查找三：平衡二叉树

  1 //平衡二叉树
  2 #include<iostream>
  3 using namespace std;
  4 
  5 typedef struct BiTNode
  6 {
  7     int data;
  8     int BF;
  9     BiTNode *lchild, *rchild;
 10 }*BiTree;
 11 
 12 // 对以p为根的二叉排序树作右旋处理，
 13 // 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 
 14 void R_Rotate(BiTree *p)
 15 {
 16     BiTree L;
 17     L = (*p)->lchild;
 18     (*p)->lchild  = L->rchild; //L的右子树挂接为P的左子树
 19     L->rchild = *p;
 20     *p = L;
 21 }
 22 
 23 // 对以p为根的二叉排序树作左旋处理，
 24 // 处理之后p指向新的树根结点，即旋转处理之前的右子树的根结点 
 25 void L_Rotate(BiTree *p)
 26 {
 27     BiTree R;
 28     R = (*p)->rchild;
 29     (*p)->rchild = R->lchild;//R的左子树挂接为P的右子树
 30     R->lchild = *p;
 31     *p = R;
 32 }
 33 
 34 //  对以指针T所指结点为根的二叉树作左平衡旋转处理 
 35 //  本算法结束时，指针T指向新的根结点 
 36 void LeftBalance(BiTree *T)
 37 {
 38     BiTree L, Lr;
 39     L = (*T)->lchild;
 40     switch(L->BF)
 41     {
 42         case 1: //新结点插在T的左孩子的左子树上,要作单右旋处理
 43             (*T)->BF = L->BF = 0; 
 44             R_Rotate(T); 
 45             break;
 46         case -1: //新结点插入在T的左孩子的右子树上,要作双旋处理
 47             Lr = L->rchild;
 48             switch(Lr->BF)
 49             {
 50                 case 1:
 51                     (*T)->BF = -1;
 52                     L->BF = 0;
 53                     break;
 54                 case 0:
 55                     (*T)->BF = 0;
 56                     L->BF = 0;
 57                     break;
 58                 case -1:
 59                     (*T)->BF = 0;
 60                     L->BF = 1;
 61                     break;
 62             }
 63             Lr->BF = 0;
 64             L_Rotate(&(*T)->lchild);
 65             R_Rotate(T);
 66     }
 67 }
 68 
 69 // 对以指针T所指结点为根的二叉树作右平衡旋转处理，
 70 // 本算法结束时，指针T指向新的根结点
 71 void RightBalance(BiTree *T)
 72 {
 73     BiTree R, Rl;
 74     R = (*T)->rchild;
 75     switch(R->BF)
 76     {
 77         case -1: //新结点插入在T的右孩子的右子树上,要作单左旋处理
 78             (*T)->BF = R->BF =0;
 79             L_Rotate(T);
 80             break;
 81         case 1: //新结点插入在T的右孩子的左子树上,要作双旋处理
 82             Rl = R->lchild;
 83             switch(Rl->BF)
 84             {
 85                 case 1:
 86                     (*T)->BF = 0;
 87                     R->BF = -1;
 88                     break;
 89                 case 0:
 90                     (*T)->BF = 0;
 91                     R->BF = 0;
 92                     break;
 93                 case -1:
 94                     (*T)->BF = 1;
 95                     R->BF = 0;
 96                     break;
 97             }
 98             Rl->BF = 0;
 99             R_Rotate(&(*T)->rchild);
100             L_Rotate(T);
101     }
102 }
103 
104 // 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 
105 // 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 
106 // 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 
107 bool InsertAVL(BiTree *T, int e, bool *taller)
108 {
109     if(!*T) //插入新的结点
110     {
111         *T = new BiTNode;
112         (*T)->data = e;
113         (*T)->lchild = (*T)->rchild = NULL;
114         (*T)->BF = 0;
115         *taller = true; //树长高
116     }
117     else
118     {
119         if(e == (*T)->data) //树中存在则不再插入
120         {
121             *taller = false;
122             return false;
123         }
124         if(e < (*T)->data) //在T的左子树中进行搜索
125         {
126             if(!InsertAVL(&(*T)->lchild,e,taller))
127                 return false;
128             if(*taller)
129             {
130                 switch((*T)->BF)
131                 {
132                     case 1: //原本左子树比右子树高
133                         LeftBalance(T);
134                         *taller = false;
135                         break;
136                     case 0: //原本左右子树等高
137                         (*T)->BF = 1;
138                         *taller = true;
139                         break;
140                     case -1: //原本左子树比右子树低
141                         (*T)->BF = 0;
142                         *taller = false;
143                         break;
144                 }
145             }
146         }
147         else
148         {
149             if(!InsertAVL(&(*T)->rchild,e,taller))
150                 return false;
151             if(*taller)
152             {
153                 switch((*T)->BF)
154                 {
155                     case 1:
156                         (*T)->BF = 0;
157                         *taller = false;
158                         break;
159                     case 0:
160                         (*T)->BF = -1;
161                         *taller = true;
162                         break;
163                     case -1:
164                         RightBalance(T);
165                         *taller = false;
166                         break;
167                 }
168             }
169         }
170     }
171     return true;
172 }
173 
174 void PreOrderPrint(BiTree T)
175 {
176     if(T==NULL)
177         return; 
178     cout<<T->data<<" ";
179     PreOrderPrint(T->lchild);
180     PreOrderPrint(T->rchild);
181 }
182 
183 int main()
184 {
185     int a[10] = {3,2,1,4,5,6,7,10,9,8};
186     BiTree T = NULL;
187     bool taller;
188     for(int i=0;i<10;i++)
189     {
190         InsertAVL(&T,a[i],&taller);
191     }
192     PreOrderPrint(T);
193 
194     return 0;
195 }