目录

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.	}