有序二杈树是很好用的，在插入和查找的时候时间复杂度一般为O（logN），但如果左右子树失去平衡，也可能达到O（N）。为了防止这种现象发生，一种解决办法是是左右子树尽量保持平衡，即建立一种平衡有序树AVL树。   一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二杈有序树。空树的高度定义为-1。 AVL树的结点声明；typedef struct avlnode{ int height;//比普通二杈有序树多了一个高度信息  ElemType data; struct bnode *lchild, *rchild;} *AvlTree, *Position; //----------AVL树基本操作------------ ------------------------------AvlTree MakeEmpty(AvlTree T);Position Find(ElemType x, AvlTree T);Position FindMin(AvlTree T);Position FindMax(AvlTree T);static int Height(Position P);AvlTree Insert(ElemType x, AvlTree T);AvlTree Delete(ElemType x, AvlTree T);ElemType Retrieve(Position P); //----------AVL树基本操作的算法实现--------------------递归算法： Position FindMin(AvlTree T){ if(T==NULL)  return NULL; else if(T->lchild == NULL)  return T; else  return FindMin(T->lchild);} Position FindMax(AvlTree T){ if(T==NULL)  return NULL; else if(T->rchild == NULL)  return T; else  return FindMax(T->rchild);}非递归算法：Position FindMin(AvlTree T){ if(T!=NULL) {  while(T->lchild != NULL)   T = T->lchild; }  return T;} Position FindMax(AvlTree T){ if(T!=NULL) {  while(T->rchild != NULL)   T = T->rchild; }  return T;}//返回P点的高度 static int Height(Position P){ if(P==NULL)  return -1; else  return P->height;}//在对一棵AVL树进行插入操作后，可能会破坏它的平衡条件，因此必须对新的AVL树进行调整，这里用到了“单旋转”或“双旋转”的算法，分别适用于：单左旋转（SingleRotateWithLeft）；对结点p的左孩子的左子树进行一次插入 单右旋转（SingleRotateWithRight）；对结点p的右孩子的右子树进行一次插入  双左旋转（DoubleRotateWithLeft）；对结点p的左孩子的右子树进行一次插入 双右旋转（DoubleRotateWithRight）；对结点p的右孩子的左子树进行一次插入  static Position SingleRotateWithLeft(Position K2){ Position K1;  K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转  K2->lchild = K1->rchild; K1->rchild = K2;  K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1; K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;  return K1;} static Position SingleRotateWithRight(Position K2){ Position K1;  K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转  K2->rchild = K1->lchild; K1->lchild = K2;  K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1; K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;  return K1;} static Position DoubleRotateWithLeft(Position K3){ K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转   return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转 }static Position DoubleRotateWithRight(Position K3){ K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转   return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转 } //向AVL树插入结点的操作 AvlTree Insert(float x, AvlTree T){ if(T == NULL) {  T = (Position)malloc(sizeof(struct avlnode));  if(T == NULL)  {   puts("wrong");    exit(1);  }  T->data = x;    T->height = 0;  T->lchild = T->rchild = NULL; } else if(T->data == x)//不做任何插入操作   ; else if(T->data > x)//把s所指结点插入到左子树中 {   T->lchild = Insert(x, T->lchild);   if(Height(T->lchild) - Height(T->rchild) == 2) //若平衡被破坏    {   if(x < T->lchild->data)     //若x比T的左孩子小，对T单左旋转      T = SingleRotateWithLeft(T);   else                         //否则，对T双左旋转       T = DoubleRotateWithLeft(T);  } } else      //把s所指结点插入到右子树中 {   T->rchild = Insert(x, T->rchild);   if(Height(T->rchild) - Height(T->lchild) == 2)   {   if(x > T->rchild->data)    //若x比T的右孩子大，对T单右旋转      T = SingleRotateWithRight(T);   else                        //否则，对T双右旋转       T = DoubleRotateWithRight(T);  } } T->height = Max(Height(T->lchild), Height(T->rchild)) + 1;  return T;   }int Max(int a, int b){ if(a>=b)  return a; else  return b;}AVL树应用示例:/*输入一组数,存储到AVL树中,并进行输出*/#include #include #define MAX 100typedef struct avlnode{ int height;//比普通二杈有序树多了一个高度信息  int data; struct avlnode *lchild, *rchild;} *AvlTree, *Position;  int Input(int a[]);//输入数据到数组,未排序 void Print(const int a[], int len); //输出未排序的原始数据AvlTree Sort(AvlTree A, const int a[], int len); //对数据进行排序 AvlTree Insert(int x, AvlTree T); //把数据存储到AVL树中Position SingleRotateWithLeft(Position K2); //单左旋转Position SingleRotateWithRight(Position K2); //单右旋转Position DoubleRotateWithLeft(Position K3);//双左旋转Position DoubleRotateWithRight(Position K3);//双右旋转int Height(Position P); //返回P点的高度int Max(int a, int b);//返回a,b中的最大值 void inorder(const AvlTree bt); //中序遍历AVL树 void PrintBT(AvlTree bt); //输出二杈树 int main(void){  int a[MAX]={0}; int len; AvlTree A=NULL;         len = Input(a); Print(a, len); printf("\n"); A = Sort(A, a, len); PrintBT(A); printf("\n"); inorder(A); system("pause");  return 0;} int Input(int a[]){ int i=0;  do {  a[i++] = rand()%1000;//输入随机数  } while(i

评论