题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805404939173888

给定一个插入序列，求一棵平衡二叉树，结果返回根结点的值，这题比较复杂，是我不会的题，重点是insert函数
几个函数列举一下

  1. 新建结点函数new_node(int v)
  2. 求树高函数get_height(node* root)
  3. 更新树高函数updata_height(node* root)
  4. 平衡因子函数get_balance_factor(node* root)，忘了这个
  5. 左旋函数L(node* &root)
  6. 右旋函数R(node* &root)
  7. 插入函数insert(node* &root, int v)

代码

  1. #include<algorithm>
  2. #include<vector>
  3. #include<cstdio>
  4. using namespace std;
  6. const int maxn = 30;
  7. struct Node{
  8.     int data, height;
  9.     Node* lchild;
  10.     Node* rchild;
  11. }*root;
  13. int n;
  15. Node* new_node(int v){
  16.     Node* node = new Node;
  17.     node->data = v;
  18.     node->height = 1;
  19.     node->lchild = node->rchild = NULL;
  20.     return node;
  21. }
  23. int get_height(Node* root){
  24.     if(root == NULL) return 0;
  25.     return root->height;
  26. }
  28. void updata_height(Node* root){
  29.     root->height = max(get_height(root->lchild),get_height(root->rchild)) + 1;
  30. }
  32. int get_balance_factor(Node* root){
  33.     return get_height(root->lchild) - get_height(root->rchild);
  34. }
  36. void L(Node* &root){
  37.     Node* temp = root->rchild;
  38.     root->rchild = temp->lchild;
  39.     temp->lchild = root;
  40.     updata_height(root);
  41.     updata_height(temp);
  42.     root = temp;
  43. }
  45. void R(Node* &root){
  46.     Node* temp = root->lchild;
  47.     root->lchild = temp->rchild;
  48.     temp->rchild = root;
  49.     updata_height(root);
  50.     updata_height(temp);
  51.     root = temp;
  52. }
  54. void insert(Node* &root, int v){
  55.     if(root == NULL){//开始插入
  56.         root = new_node(v);
  57.         return;
  58.     }
  59.     if(v < root->data){//如果小于根结点
  60.         insert(root->lchild, v);
  61.         updata_height(root);
  62.         if(get_balance_factor(root) == 2){
  63.             if(get_balance_factor(root->lchild) == 1){
  64.                 R(root);
  65.             } else if(get_balance_factor(root->lchild) == -1){
  66.                 L(root->lchild);
  67.                 R(root);
  68.             }
  69.         } 
  70.     } else {//如果比根结点大
  71.         insert(root->rchild, v);
  72.         updata_height(root);    
  73.         if(get_balance_factor(root) == -2){
  74.             if(get_balance_factor(root->rchild) == -1){
  75.                 L(root);
  76.             } else if(get_balance_factor(root->rchild) == 1){
  77.                 R(root->rchild);
  78.                 L(root);
  79.             }
  80.         }
  81.     }
  82. }
  84. int main(){
  85.     scanf("%d",&n);
  86.     int num;
  87.     for(int i = 0; i < n; i++){
  88.         scanf("%d",&num);
  89.         insert(root, num);
  90.     }
  91.     printf("%d\n", root->data);
  92.     return 0;
  93. }