当前位置: 代码迷 >> 综合 >> PAT1066 Root of AVL Tree (25)(AVL树)
  详细解决方案

PAT1066 Root of AVL Tree (25)(AVL树)

热度:93   发布时间:2024-01-16 13:20:43.0

题意:

给出一系列要插入平衡搜索二叉树的数,要求输出最后的根节点

思路:

没其他办法,完完全全是AVL树的插入节点模拟,这题就不会写,看别人代码写的。

#include<iostream>
#include<algorithm>
using namespace std;struct node {int key;struct node *left, *right;
};node *rotateLeft(node *root) {	//左单旋转node *t = root->right;		root->right = t->left;t->left = root;return t;
}
node *rotateRight(node *root) {	//右单旋转node *t = root->left;root->left = t->right;t->right = root;return t;
}
int getHeight(node *root) {if (root == nullptr)return 0;return max(getHeight(root->left), getHeight(root->right)) + 1;
}
node *rotateLR(node *root) {	//LR平衡旋转root->left = rotateLeft(root->left);return rotateRight(root);
}
node *rotateRL(node *root) {	//RL平衡旋转root->right = rotateRight(root->right);return rotateLeft(root);
}
node *insert(node *root, int key) {if (root == nullptr) {root = new node();root->key = key;root->left = nullptr;root->right = nullptr;} else if (key < root->key) {root->left = insert(root->left, key);//递归插入并平衡if (getHeight(root->left) - getHeight(root->right) == 2) {if (key < root->left->key) {	//在根节点的左孩子的左子树上插入root = rotateRight(root);} else {			//在根节点的左孩子的右子树上插入root = rotateLR(root);		}}} else {root->right = insert(root->right, key);if (getHeight(root->right) - getHeight(root->left) == 2) {if (key > root->right->key) {	//在根节点的右孩子的右子树上插入root = rotateLeft(root);} else {			//在根节点的右孩子的左子树上插入root = rotateRL(root);}}}return root;
}int main() {int n, key;scanf("%d", &n);node *root = nullptr;for (int i = 0; i < n; i++) {scanf("%d", &key);root = insert(root, key);}printf("%d", root->key);return 0;
}

  相关解决方案