在搜索一定量的资料后发现有两种构建方式，其中一种是设置parent指针，从而能在将节点穿插到最下面后进行回溯，只实际上是最朴素的做法。
我们采用第二种做法，就是将AVL树的构建用递归回溯的方法进行，顺序是这样：首先插入节点，接着检查这个节点是否满足balance，不满足则进行旋转，之后再更新节点的高度（不管有没有旋转） ， 这个递归实际上就是不断向下直到递归到了最底层，然后将节点插入到最底层之后就会有一个回溯，回溯过程刚好也能满足求高度的条件（下面的节点的高度都已经求出来了），因此能够顺便把沿途每个节点的高度都求出来，但是我们每次并不急着求高度，而是先判断符不符合要求，并且进行旋转。因为如果我们先去求高度的话得到的点旋转后会变，就会使得操作无效。这个过程之中我们便可以将沿路上的不满足平衡的节点全部都给弄平衡了。注意旋转中里面需要更新高度，因为有的节点高度会变。
还有很关键的一点，AVL树某个节点为根变换时这个位置的根节点变了，但其高度不变，这可以避免退化出现平衡因子绝对值大于2的情况
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct AVLNode { char data; int height; struct AVLNode *lchild , *rchild; }AVLNode; int Height(AVLNode* node) { if(node == NULL) return 0; else return node -> height; } int Max(int a , int b) { if(a > b) return a; else return b; } AVLNode* LL(AVLNode** T) { AVLNode* son = (*T) -> lchild; (*T) -> lchild = son -> rchild; son -> rchild = (*T); (*T) -> height = Max(Height((*T) -> lchild) , Height((*T) -> rchild)) + 1; son -> height = Max(Height(son -> lchild) , Height(son -> rchild)) + 1; return son; } AVLNode* RR(AVLNode** T) { AVLNode* son = (*T) -> rchild; (*T) -> rchild = son -> lchild; son -> lchild = (*T); (*T) -> height = Max(Height((*T) -> lchild) , Height((*T) -> rchild)) + 1; son -> height = Max(Height(son -> lchild) , Height(son -> rchild)) + 1; return son; } AVLNode* RL(AVLNode** T) { AVLNode* son = (*T) -> rchild -> lchild; (*T) -> rchild = LL(&((*T) -> rchild)); (*T) = RR(T); return son; } AVLNode* LR(AVLNode** T) { AVLNode* son = (*T) -> lchild -> rchild; (*T) -> lchild = RR(&((*T) -> lchild)); (*T) = LL(T); return son; } void Insert(AVLNode** T , char x) { if((*T) == NULL) { AVLNode* p = (AVLNode*) malloc (sizeof(AVLNode)); p -> data = x; p -> lchild = NULL; p -> rchild = NULL; p -> height = 1; (*T) = p; return; } else { if(x < (*T) -> data) { Insert(&((*T) -> lchild) , x); if(Height((*T) -> lchild) - Height(((*T) -> rchild)) > 1) { if((*T) -> lchild -> data < x) (*T) = LR(T); else (*T) = LL(T); } } else if(x > (*T) -> data) { Insert(&((*T) -> rchild) , x); if(Height((*T) -> lchild) - Height(((*T) -> rchild)) < -1) { if((*T) -> rchild -> data < x) (*T) = RR(T); else (*T) = RL(T); } } (*T) -> height = Max(Height((*T) -> lchild) , Height((*T) -> rchild)) + 1; } } void Print(AVLNode* T , int layer) { if(T != NULL) { Print(T -> rchild, layer + 1); for(int i = 0 ; i < layer ; i ++) printf(" "); printf("%c\n" , T -> data); Print(T -> lchild , layer + 1); } } void Pre_print(AVLNode* T) { if(T != NULL) { printf("%c" , T -> data); Pre_print(T -> lchild); Pre_print(T -> rchild); } } void Mid_print(AVLNode* T) { if(T != NULL) { Mid_print(T -> lchild); printf("%c" , T -> data); Mid_print(T -> rchild); } } void Post_print(AVLNode* T) { if(T != NULL) { Post_print(T -> lchild); Post_print(T -> rchild); printf("%c" , T -> data); } } int main() { char a[100]; scanf("%s" , a); AVLNode* T = NULL; for(int i = 0 ; i < strlen(a) ; i ++) { Insert(&T , a[i]); } printf("Preorder: "); Pre_print(T); printf("\n"); printf("Inorder: "); Mid_print(T); printf("\n"); printf("Postorder: "); Post_print(T); printf("\n"); printf("Tree:\n"); Print(T , 0); return 0; }
