数据结构与算法系列研究五——树、二叉树、三叉树、平衡排序二叉树AVL(5)

View Code

4.4．理论与测试

理论：如图，给定一个序列的结点链表，按照几种变换规则得到了下图的排序二叉树，可以得到三序遍历和平衡因子。（由于图形非常多，暂时为手工画图）

该序列为：47, 63, 54,28,31,14,26,53,99,81

先序遍历：31，26二叉排序树 数据结构，14，28，54，47，53，81，63，99

中序遍历：14，26，28，31，47，53，54，63，81，99

平衡因子：31和47的平衡因子为-1，其他的都为0

测试：运行程序以后输出为：

由先序和中序序列可以还原出树的原型，对照可知结果是恰当的。

4.5．讨论与体会

排序二叉树的中序遍历结果即为降序排列，但是运算速度不是最高的，为了寻求更好的方式，平衡排序二叉树便问世了。对于开创者而言这是倍感质疑的，但是针对后专家来说，在学习算法的核心观念的同时，更重要的是对方是怎么想起的，当一个现实生活的还要放到眼前是，我们要有推动的心态，具有变革能力，这点是比较重要的，因为针对应用上来说有了第一个其他的就不再令人惊奇了。同时，递归，引用，开关、选择分支语句的利用也要引起注意。学习图的最好方法，就是数形结合，

一定要多画图。

4.6．附录（源代码）

  1 #include<stdio.h> 
  2 #include<stdlib.h>
  3 #include<iostream>
  4 using namespace std;
  5 #define LH  1//左边高
  6 #define EH  0//一样高
  7 #define RH  -1//右边高
  8 typedef struct BSTNode
  9 {
 10   int data;//信息
 11   int bf;//平衡因子
 12   struct BSTNode *lchild,*rchild; //平衡树左右儿子指针
 13 }BSTNode,*BSTree;//平衡二叉排序树结构的定义
 14  
 15 void R_Rotate(BSTree &p)  
 16 {
 17     //对以*p为根的二叉排序树做右旋处理，处理之后p指向新的树根结点
 18     //注意此处引用的好处就是不用再出现双亲指针
 19    BSTree lc;
 20    lc=p->lchild; //指向B的位置
 21    p->lchild=lc->rchild; //此处转换仍保持中序遍历不变性
 22    lc->rchild=p; //更改a的指针位置
 23    p=lc;        //lc变成新的a
 24 }  
 25 void L_Rotate(BSTree &p)  
 26 {
 27     //对以*p为根的二叉排序树做左旋处理，处理之后p指向新的树根结点
 28     //和R_Rotate()镜像对称
 29    BSTree rc;    
 30    rc = p->rchild;
 31    p->rchild = rc->lchild;
 32    rc->lchild = p;
 33    p = rc;    
 34 }  
 35 //包含LL和LR
 36 void LeftBalance(BSTree &T)     
 37 {  //对已*T为根的二叉排序树做左平衡旋转处理
 38    BSTree lc,rd;
 39    lc = T->lchild; //lc调整左边
 40    switch(lc->bf)  
 41    {
 42      case LH://若是左边高则为LL型，只需旋转即可
 43          T->bf = lc->bf = EH; //旋转后平衡因子均为0
 44          R_Rotate(T); //LL型需要右旋转
 45          break;  
 46      case RH://若是右边高，则为LR型，需分两步调整
 47          rd = lc->rchild; //找到不确定因子rd
 48          switch(rd->bf)//对不确定因子进行讨论
 49          {
 50            case LH://左边高调整后
 51              T->bf = RH;//根节点右边变高
 52              lc->bf = EH; //lc变平衡
 53              break;
 54           case EH://rd有左右节点
 55             T->bf = lc->bf = EH; //调整后持平
 56             break;
 57           case RH://右边高
 58             T->bf = EH;//根节点平衡
 59             lc->bf = LH;//lc节点变成左边高
 60             break;  
 61          }  
 62         rd->bf=EH; //调整后rd节点一定平衡，且变成新的头节点
 63         L_Rotate(T->lchild); //1.先左旋
 64         R_Rotate(T);         //2.再右旋
 65    }
 66 }  
 67 /*************右平衡操作，包含RR和RL*******************************/
 68 void RightBalance(BSTree &T)  
 69 {
 70     //对已*T为根的二叉排序树做右平衡旋转处理
 71     //因为为LeftBalance(BSTree &T)的镜像，注释则省略
 72    BSTree lc,rd;
 73    lc = T->rchild;
 74    switch(lc->bf)
 75    {
 76     case RH://右边高，RR型
 77         T->bf = lc->bf = EH;
 78         L_Rotate(T);
 79         break;
 80     case LH://左边高，RL型，分两步旋转
 81        rd = lc->lchild;
 82        switch(rd->bf)
 83        {  
 84         case RH:
 85            T->bf = LH;
 86            lc->bf = EH;
 87            break;
 88         case LH:
 89            T->bf = EH;
 90            lc->bf = RH;
 91            break;
 92        case EH:
 93            T->bf = lc->bf = EH;
 94            break;
 95        }
 96        rd->bf = EH;
 97        R_Rotate(T->rchild); //1.先右旋
 98        L_Rotate(T);         //2.再左旋
 99    }
100 }
101  
102 int InsertAVL(BSTree &T, int key, bool &taller)  
103 {
104 //若在平衡二叉排序树中不存在与关键字key相等的结点，则将关键字插入树中
105 //布尔变量taller表示树是否“长高”
106   if(T==NULL)
107   {
108     T = (BSTree)malloc(sizeof(BSTNode));
109     T->data = key;
110     T->bf = EH;//叶子结点其平衡因子肯定为0
111     T->lchild = T->rchild = NULL;
112     taller = 1;//树长高了
113   }
114   else
115   {
116      if(key==T->data)
117      {//如果树中已存放此关键字则不予插入
118        taller = 0;
119        return 0;
120      }
121      if(key<T->data)
122      {//关键字小于根结点则插入其左子树中
123           if(!InsertAVL(T->lchild,key,taller))
124                return 0;
125           if(taller)
126           {//如果树长高了，判断是否平衡
127             switch(T->bf)
128             {
129              case LH://若左边高，这次又加上一个左边的节点，则肯定变为2，即需要调整
130                  LeftBalance(T);//不平衡时调用左平衡函数，使左子树平衡
131                  taller = 0;
132                  break;
133              case EH://若相等，在左边加一个节点，则变为左边高
134                 T->bf = LH;
135                 taller = 1; //树变高
136                 break;
137              case RH://若右边高，在左边加一个节点，则持平
138                 T->bf = EH;
139                 taller = 0;
140                break;
141             }
142           }
143      }
144      else
145      {//插入右子树中
146         if(!InsertAVL(T->rchild,key,taller))
147           return 0;
148         if(taller)
149         {
150           switch(T->bf)
151           {
152             case LH://同理，本来左边高，在右边加一个节点则持平
153                 T->bf = EH;
154                 taller = 0;
155                 break;
156             case EH://右边变高
157                 T->bf = RH;
158                 taller = 1;
159                 break;
160             case RH://右边不平衡了，需要调整
161                 RightBalance(T);
162                 taller = 0;
163                 break;
164           }
165         }
166      }
167   }
168         return 1;
169 }  
170 //访问函数，输出节点以及相应平衡因子
171 void VisitTree(BSTree &T)
172 {  //输出结点
173     if(T!=NULL)  
174     {
175       printf("%d ",T->data);  
176       printf("平衡因子: %d\n",T->bf);    
177     }
178 }  
179 
180 void PreOrderTraverse(BSTree &T)
181 {//递归实现先序遍历
182     if(T!=NULL)
183     VisitTree(T);
184     if(T->lchild)
185       PreOrderTraverse(T->lchild);
186     if(T->rchild)
187      PreOrderTraverse(T->rchild);
188 }  
189 
190 void InOrderTraverse(BSTree &T)
191 {//递归实现中序遍历
192     if(T->lchild)
193       InOrderTraverse(T->lchild);
194     if(T!=NULL)
195        VisitTree(T);
196     if(T->rchild)
197       InOrderTraverse(T->rchild);
198 }  
199 int main(  )
200 {
201     BSTree T;
202     bool taller=0;
203     int i;
204     T=NULL;
205     int  a[50]={47,63,54,28,31,14,26,53,99,81};
206     for(i=0;i<10;i++)
207     {
208         InsertAVL(T,a[i],taller);   
209     }
210      printf("先序遍历:\n");   
211      PreOrderTraverse(T);    
212      printf("\n中序遍历:\n");
213      InOrderTraverse(T);    
214      printf("\n");
215      return 0;
216 }

View Code

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-121392-5.html