題意:

給出一系列要插入平衡搜索二叉樹的數，要求輸出最后的根節點

思路：

沒其他辦法，完完全全是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; }

轉載于:https://www.cnblogs.com/seasonal/p/10343620.html

總結

以上是生活随笔為你收集整理的PAT1066 Root of AVL Tree (25)(AVL树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。