1 #include <iostream>  2 #include <algorithm>  3 #include <stdlib.h>  4 using namespace std;  5 typedef struct AVLTree{  6     int data;  7     struct AVLTree *lchild, *rchild;  8     int height;  9 }AVLTree, *PAVLTree; 10 int getHeight(PAVLTree T) 11 { 12     int height = 0; 13     if (T != NULL) 14     { 15         height = 1; 16         if (T->lchild != NULL) 17             height = T->lchild->height + 1; 18         if (T->rchild != NULL) 19             height = max(height, T->rchild->height) + 1; 20     } 21     return height; 22     //recursion version 23 //    if (T != NULL) 24 //        return max(getHeight(T->lchild), getHeight(T->rchild)) + 1; 25 //    else 26 //        return 0; 27 } 28 //LL type 29 PAVLTree SingleLeft(PAVLTree A) 30 { 31     PAVLTree B = A->lchild; 32     A->lchild = B->rchild; 33     B->rchild = A; 34     A->height = max(getHeight(A->lchild), getHeight(A->rchild)) + 1; 35     B->height = max(getHeight(B->lchild), getHeight(B->rchild)) + 1; 36     return B; 37 } 38 //RR type 39 PAVLTree SingleRight(PAVLTree A) 40 { 41     PAVLTree B = A->rchild; 42     A->rchild = B->lchild; 43     B->lchild = A; 44     //update height 45     A->height = max(getHeight(A->lchild), getHeight(A->rchild)); 46     B->height = max(getHeight(B->lchild), getHeight(B->rchild)); 47     return B; 48 } 49 //LR type 50 PAVLTree Double_Left_Right(PAVLTree A) 51 { 52     A->lchild = SingleRight(A->lchild); 53     return SingleLeft(A); 54 } 55 //RL type 56 PAVLTree Double_Right_Left(PAVLTree A) 57 { 58     A->rchild = SingleLeft(A->rchild); 59     return SingleRight(A); 60 } 61 //insert function 62 PAVLTree insert_AVL_tree(int data, PAVLTree T) 63 { 64     //the process same as binary search tree, but keep balance of the tree after inserted data 65     if (T == NULL) 66     { 67         T = (PAVLTree)malloc(sizeof(AVLTree)); 68         T->data =http://www.mamicode.com/ data; 69         T->lchild = T->rchild = NULL; 70         T->height = 0; 71     } 72     if (data < T->data) 73     { 74         T->lchild = insert_AVL_tree(data, T->lchild); 75         //if can not meeting the conditions 76         if (getHeight(T->lchild) - getHeight(T->rchild) == 2) 77         { 78             if (data < T->lchild->data) 79             { 80                 T = SingleLeft(T); 81             } 82             else 83                 T = Double_Left_Right(T); 84         } 85     } 86     //if can not meeting the conditions 87     else if (data > T->data) 88     { 89         T->rchild = insert_AVL_tree(data, T->rchild); 90         if (getHeight(T->lchild) - getHeight(T->rchild) == -2) 91         { 92             if (data > T->rchild->data) 93                 T = SingleRight(T); 94             else 95                 T = Double_Right_Left(T); 96         } 97     } 98     //update the height 99     T->height = max(getHeight(T->lchild), getHeight(T->rchild)) + 1;100 101     return T;102 103 104 }105 //previous order traverse106 void preOrderTraverse(PAVLTree T)107 {108     if (T != NULL)109     {110         cout << T->data << " ";111         preOrderTraverse(T->lchild);112         preOrderTraverse(T->rchild);113     }114 }115 int main()116 {117     int n;118     cin >> n;//the number of test data119     int t;120     PAVLTree root = NULL;121     for (int i = 0; i < n; i++)122     {123         cin >> t;124         root = insert_AVL_tree(t, root);//create the AVL tree125     }126     preOrderTraverse(root);//show the result127     return 0;128 }