AVL树的定义以及基本操作（完美版）

#include "avlTree.h" int Max(int a,int b) { return a>b?a:b; } avlTree SingleRotateWithLeft(avlTree k2) { avlTree k1; k1 = k2->lchild; k2->lchild = k1->rchild; k1->rchild = k2; return k1; } avlTree SingleRotateWithRight(avlTree k2) { avlTree k1; k1 = k2->rchild; k2->rchild = k1->lchild; k1->lchild = k2; return k1; } avlTree DoubleRotateWithLeft(avlTree k1) { k1->lchild = SingleRotateWithRight(k1->lchild); return SingleRotateWithLeft(k1); } avlTree DoubleRotateWithRight(avlTree k1) { k1->rchild = SingleRotateWithLeft(k1->rchild); return SingleRotateWithRight(k1); } avlTree Insert(avlTree T,ElemType e) { if (T == NULL) { T = (avlTree)malloc(sizeof(avlNode)); if(!T) { printf("Insert: T malloc error!\n"); system("pause"); exit(-1); } T->data = e; T->lchild = NULL; T->rchild = NULL; } else if(e < T->data) { T->lchild = Insert(T->lchild,e); if (Depth(T->lchild) - Depth(T->rchild) == 2) { if(e<T->lchild->data) { T = SingleRotateWithLeft(T); } else { T = DoubleRotateWithLeft(T); } } } else if(e > T->data) { T->rchild = Insert(T->rchild,e); if (Depth(T->rchild) - Depth(T->lchild) == 2) { if(e>T->rchild->data) { T = SingleRotateWithRight(T); } else { T = DoubleRotateWithRight(T); } } } return T; } avlTree MakeEmpty(avlTree T) { if(T != NULL) { T->lchild = MakeEmpty(T->lchild); T->rchild = MakeEmpty(T->rchild); free(T); } return NULL; } avlTree Find(avlTree T,ElemType e) { if(T == NULL) { return NULL; } else if(e<T->data) { T->lchild = Find(T->lchild,e); } else if(e>T->data) { T->rchild = Find(T->rchild,e); } return T; } avlTree FindMin(avlTree T) { if(T == NULL) { return NULL; } while(T->lchild != NULL) { T = T->lchild; } return T; } avlTree FindMax(avlTree T) { if(T == NULL) { return NULL; } while(T->rchild != NULL) { T = T->rchild; } return T; } int Depth(avlTree T) { int rDepth,lDepth; if(T == NULL) { return 0; } lDepth = Depth(T->lchild) + 1; rDepth = Depth(T->rchild) + 1; return lDepth>rDepth ? lDepth : rDepth; } avlTree Delete(avlTree T,ElemType e) { if(T == NULL) { return NULL; } else if(e < T->data) { T->lchild = Delete(T->lchild,e); if(Depth(T->rchild) - Depth(T->lchild) == 2) { if (Depth(T->rchild->rchild) < Depth(T->rchild->lchild)) { T = DoubleRotateWithRight(T); } else { T = SingleRotateWithRight(T); } } } else if(e > T->data) { T->rchild = Delete(T->rchild,e); if(Depth(T->lchild) - Depth(T->rchild) == 2) { if(Depth(T->lchild->lchild) < Depth(T->lchild->rchild)) { T = DoubleRotateWithLeft(T); } else { T = SingleRotateWithLeft(T); } } } else if(T->lchild == NULL && T->rchild == NULL) { free(T); return NULL; } else { avlTree tmp = FindMin(T->rchild); T->data = tmp->data; T->rchild = Delete(T->rchild,tmp->data); } return T; } void preOrderTraverse(avlTree T) { if(T == NULL) { return; } printf("%d ",T->data); preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); } void inOrderTraverse(avlTree T) { if(T == NULL) { return; } inOrderTraverse(T->lchild); printf("%d ",T->data); inOrderTraverse(T->rchild); } void postOrderTraverse(avlTree T) { if(T == NULL) { return; } postOrderTraverse(T->lchild); postOrderTraverse(T->rchild); printf("%d ",T->data); } void levelOrderTraverse(avlTree T) { if(T == NULL) { return; } que_init(&Que,20); que_push(&Que,T); while(Que.rear != Que.front) { avlTree tmp; que_pop(&Que,&tmp); printf("%d ",tmp->data); if(tmp->lchild) { que_push(&Que,tmp->lchild); } if(tmp->rchild) { que_push(&Que,tmp->rchild); } } printf("\n"); }