二叉树的存储实现与遍历和左右旋转

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