AVL Tree

avlTree.h

  1 #ifndef AVLTREE_H
  2 #define AVLTREE_H
  3 
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 #include <malloc.h>
  7 #include <queue>
  8 
  9 #define LH +1
 10 #define EH 0
 11 #define RH -1
 12 
 13 typedef int ElemType;
 14 typedef struct BSTNode//平衡二叉排序树结构体
 15 {
 16     ElemType data;
 17     int bf;
 18     struct BSTNode *lchild,*rchild;
 19 }BSTNode, *BSTree;
 20 typedef enum{ERROR,OK}Status;
 21 
 22 void R_Rotate(BSTree &T)//右旋操作
 23 {
 24     BSTree lc = T->lchild;
 25     T->lchild = lc->rchild;
 26     lc->rchild = T;
 27     T = lc;
 28 }
 29 
 30 void L_Rotate(BSTree &T)//左旋操作
 31 {
 32     BSTree rd = T->rchild;
 33     T->rchild = rd->lchild;
 34     rd->lchild = T;
 35     T = rd;
 36 }
 37 
 38 bool LT(ElemType e1,ElemType e2)
 39 {
 40     return e1 < e2;
 41 }
 42 
 43 bool GT(ElemType e1,ElemType e2)
 44 {
 45     return e1 > e2;
 46 }
 47 
 48 void LBalance(BSTree &T)//平衡左子树
 49 {
 50     BSTree lc = T->lchild;
 51     switch(lc->bf)
 52     {
 53     case LH:
 54         R_Rotate(T);
 55         T->bf = lc->bf = EH;
 56         break;
 57     case RH:
 58         BSTree rd = lc->rchild;
 59         switch(rd->bf)
 60         {
 61         case LH:
 62             T->bf = RH;
 63             lc->bf = EH;
 64             break;
 65         case EH:
 66             T->bf = lc->bf = EH;
 67             break;
 68         case RH:
 69             T->bf = EH;
 70             lc->bf = LH;
 71             break;
 72         }
 73         rd->bf = EH;
 74         L_Rotate(T->lchild);
 75         R_Rotate(T);
 76         break;
 77     }
 78 }
 79 
 80 void RBalance(BSTree &T)//平衡右子树
 81 {
 82     BSTree rd = T->rchild;
 83     switch(rd->bf)
 84     {
 85     case RH:
 86         T->bf = rd->bf = EH;
 87         L_Rotate(T);
 88         break;
 89     case LH:
 90         BSTree lc = rd->lchild;
 91         switch(lc->bf)
 92         {
 93         case LH:
 94             T->bf = EH;
 95             rd->bf = RH;
 96             break;
 97         case EH:
 98             T->bf = rd->bf = EH;
 99             break;
100         case RH:
101             T->bf = LH;
102             rd->bf = EH;
103             break;
104         }
105         lc->bf = EH;
106         R_Rotate(T->rchild);
107         L_Rotate(T);
108     }
109 }
110 
111 bool InsertAVLTree(BSTree &T,ElemType e,bool &taller)//插入节点，若要平衡则进行相应平衡处理
112 {
113     if(!T)
114     {
115         T = (BSTree)malloc(sizeof(BSTNode));
116         T->data = e;
117         T->bf = EH;
118         T->lchild = T->rchild = NULL;
119         taller = true;
120         return true;
121     }
122     else if(e == T->data)
123     {
124         taller = false;
125         return false;
126     }
127     else if(LT(e,T->data))
128     {
129         if(!InsertAVLTree(T->lchild,e,taller))
130         {
131             return false;
132         }
133         if(taller)
134         {
135             switch(T->bf)
136             {
137             case EH:
138                 T->bf = LH;
139                 taller = true;
140                 break;
141             case LH:
142                 LBalance(T);//右旋转
143                 taller = false;
144                 break;
145             case RH:
146                 T->bf = EH;
147                 taller = false;
148                 break;
149             }
150             return true;
151         }
152     }
153     else
154     {
155         if(!InsertAVLTree(T->rchild,e,taller))
156         {
157             return false;
158         }
159         if(taller)
160         {
161             switch(T->bf)
162             {
163             case EH:
164                 T->bf = RH;
165                 taller = true;
166                 break;
167             case LH:
168                 T->bf = EH;
169                 taller = false;
170                 break;
171             case RH:
172                 RBalance(T);
173                 taller = false;
174                 break;
175             }
176             return true;
177         }
178     }
179 }
180 
181 Status LevelTraverseAVLTree(BSTree T)//二叉排序树层序遍历
182 {
183     std::queue<BSTree> qbi;
184     BSTree p;
185 
186     if(T)//逻辑要判断准确
187     {
188         qbi.push(T);
189         while(!qbi.empty())
190         {
191             p = qbi.front();
192             printf("%d ",p->data);
193             qbi.pop();
194             if(p->lchild)
195             {
196                 qbi.push(p->lchild);
197             }
198             if(p->rchild)
199             {
200                 qbi.push(p->rchild);
201             }
202         }
203         printf("\n");
204     }
205     return OK;
206 }
207 
208 #endif

main.cpp

 1 #include "avlTree.h"
 2 
 3 int main()
 4 {
 5     BSTree T = NULL;
 6     bool taller;
 7     int a[5] = {13,24,37,90,53};
 8     for(int i = 0;i < 5;i++)
 9     {
10         InsertAVLTree(T,a[i],taller);
11     }
12     LevelTraverseAVLTree(T);
13 
14     system("pause");
15     return 0;
16 }