平衡二叉树代码(c++)
时间: 2023-12-21 09:03:56 浏览: 42
以下是C++实现的平衡二叉树代码:
```c++
#include<bits/stdc++.h>
using namespace std;
struct Node {
int val, height;
Node *left, *right;
Node(int v): val(v), height(1), left(nullptr), right(nullptr) {}
};
int getHeight(Node *root) {
return root ? root->height : 0;
}
int getBalanceFactor(Node *root) {
return getHeight(root->left) - getHeight(root->right);
}
void updateHeight(Node *root) {
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
}
void L(Node *&root) {
Node *temp = root->right;
root->right = temp->left;
temp->left = root;
updateHeight(root);
updateHeight(temp);
root = temp;}
void R(Node *&root) {
Node *temp = root->left;
root->left = temp->right;
temp->right = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void insert(Node *&root, int val) {
if (!root) {
root = new Node(val);
return;
}
if (val < root->val) {
insert(root->left, val);
updateHeight(root);
if (getBalanceFactor(root) == 2) {
if (getBalanceFactor(root->left) == 1) {
R(root);
} else if (getBalanceFactor(root->left) == -1) {
L(root->left);
R(root);
}
}
} else {
insert(root->right, val);
updateHeight(root);
if (getBalanceFactor(root) == -2) {
if (getBalanceFactor(root->right) == -1) {
L(root);
} else if (getBalanceFactor(root->right) == 1) {
R(root->right);
L(root);
}
}
}
}
int main() {
Node *root = nullptr;
int n, val;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> val;
insert(root, val);
}
return 0;
}
```