AVL树结点的定义
1. typedef int TElmType; 2. typedef struct avl_node{ 3. TElmType data; 4. struct avl_node* lchild; 5. struct avl_node* rchild; 6. int height; 7. } AVLNode, *AVLTree;
产生一个结点
1. AVLTree create_node(AVLElem data){ 2. AVLTree p; 3. p=(AVLTree)malloc(sizeof( AVLNode)); // void * 空指针为万能指针 4. p->data=data; 5. p->rchild=NULL; 6. p->lchild=NULL; 7. p->height=1; //用于判断和矫正树的高度 8. return p; 9.}
实现前序遍历二叉树
1. void pre_order(AVLTree root) { 2. if (root != NULL) { 3. printf("%d-", root->data); 4. printf("(%d)",root->height); 5. pre_order(root->lchild); 6. pre_order(root->rchild); 7. } 8. }
右旋的实现
1. static AVLTree right_rotation(AVLTree root){ 2. AVLTree z=root; 3. AVLTree y=z->lchild; 4. AVLTree T3=y->lchild; 5. y->rchild=z; 6. z->lchild=T3; 7. z->height=max(get_height(z->lchild), get_height(z->rchild))+1; //孩子的高度加一即为父子树的高度 8. y->height=max(get_height(y->lchild), get_height(y->rchild))+1; 9. return y; 10. }
左旋的实现
1. static AVLTree left_rotation(AVLTree root){ 2. AVLTree z=root; 3. AVLTree y=z->rchild; 4. AVLTree T2=y->lchild; 5. y->lchild=z; 6. z->rchild=T2; // 将本来z->rchlid覆盖 7. z->height=max(get_height(z->lchild), get_height(z->rchild))+1; //孩子的高度加一即为父子树的高度 8. y->height=max(get_height(y->lchild), get_height(y->rchild))+1; 9. return y; 10. }
