1. /**
2. *       目的：实现AVL
3. *       利用数组对左右儿子简化代码，但是对脑力难度反而增大不少，只适合acm模板
4. *       其实avl在acm中基本不用，基本被treap取代
5. *       avl一般只要求理解思路，不要求写出代码，因为真心很烦
6. */
7.  
8. #include <iostream>
9. #include <cstdio>
10. #include <algorithm>
11. #include <cstring>
12. #include <string>
13. #include <time.h>
14. #include <queue>
15. using namespace std;
16.  
17. int COUNT;      //统计树中不重复节点的个数
18. int HEIGHT; //统计数的高度
19.  
20. //数据节点
21. class DNode
22. {
23. public:
24.         int data;
25.         DNode():data(0){};
26.         DNode(int d):data(d){}
27.  
28.         bool operator = (const DNode &d){
29.                 return data = d.data;
30.         }
31.         bool operator == (const DNode &d){
32.                 return data == d.data;
33.         }
34.         bool operator > (const DNode &d){
35.                 return data > d.data;
36.         }
37.         bool operator < (const DNode &d){
38.                 return data < d.data;
39.         }
40.         void show(){
41.                 cout << endl;
42.                 cout << "***************" << endl;
43.                 cout << "data: " << data << endl;
44.         }
45. };
46. //treap的节点
47. template<class T>
48. class AVLNode{
49. private:
50.         int hgt;        //节点的高度
51. public:
52.         T data;
53.         int count;
54.        
55.         AVLNode<T> *son[2];     //0是左儿子，1是右儿子
56.         AVLNode<T>(T data):data(data), count(1){
57.                 son[0] = son[1] = NULL;
58.                 hgt = 1;
59.         }
60.  
61.         int max(int a, int b){return a > b ? a : b;}
62.         void show(){
63.                 data.show();
64.                 cout << "c hgt: " << this->height() << endl;
65.                 cout << "l hgt: " << this->son[0]->height() << endl;
66.                 cout << "r hgt: " << this->son[1]->height() << endl;
67.                 cout << "count: " << count << endl;
68.                 cout << endl;
69.         }
70.         int height(){
71.                 if(NULL == this)
72.                         return 0;
73.                 return _getHeight(this);
74.         }
75.         int _getHeight(AVLNode<T> * cur){
76.                 if(NULL == cur)
77.                         return 0;
78.                 return 1 + max(_getHeight(cur->son[0]), _getHeight(cur->son[1]));
79.         }
80.         void setHeight(){
81.                 hgt = _getHeight(this);
82.         }
83. };
84.  
85. //AVL Tree
86. //这里的T是节点中的数据类型
87. template<class T>
88. class AVLTree{
89. private:
90.         AVLNode<T> * root;              //根节点
91.         int hgt;                        //树的高度
92.         int size;                       //树中不重复节点数量
93.         void _insert(AVLNode<T> *& cur, T data);
94.         void _mid_travel(AVLNode<T> *cur);
95.         //层次遍历
96.         void _cengci_travel(AVLNode<T> *cur);
97.         //单旋转（左左，右右）, 左旋不是想左旋转的意思， 而是由于左子树的左儿子的高度太大
98.         //与treap的旋转命名相反
99.         void _singleRoate(AVLNode<T> *& cur, int dir);
100.         //双旋转（两次单旋转）
101.         void _doubleRoate(AVLNode<T> *& cur, int dir);
102.         int max(int a, int b){
103.                 return a > b ? a : b;
104.         }
105. public:
106.         AVLTree():root(NULL), hgt(0){}
107.         void insert(const T & data);
108.         void mid_travel();
109.         int height(){
110.                 return root->height();
111.         }
112.         //层次遍历
113.         void cengci_travel(){
114.                 _cengci_travel(root);
115.         };
116.  
117. };
118.  
119. /*************  私有方法开始**********************/
120. template<class T>
121. void AVLTree<T>::_insert(AVLNode<T> *& cur, T data){
122.         if(NULL == cur){
123.                 cur = new AVLNode<T>(data);
124.         }else if(data == cur->data){
125.                 cur->count++;
126.         }else{
127.                 int dir = (data > cur->data);
128.                 _insert(cur->son[dir], data);
129.                 if(2 <= cur->son[dir]->height() - cur->son[!dir]->height()){
130.                         bool lr = (data > cur->data);
131.                         lr ? _singleRoate(cur, dir) : _doubleRoate(cur, dir);
132.                 }
133.         }
134.         cur->setHeight();
135.         //cout << "set height: " << endl;
136.         //cur->show();
137. }
138. template<class T>
139. void AVLTree<T>::_mid_travel(AVLNode<T> * cur){
140.         if(NULL != cur){
141.                 //先查找做子树
142.                 _mid_travel(cur->son[0]);
143.                 //if(abs(cur->son[0]->height() - cur->son[1]->height()) >= 2)
144.                 {
145.                         cur->show();
146.                 }
147.                 _mid_travel(cur->son[1]);
148.         }
149. }
150. //层次遍历，
151. //如果节点为空就输出0 来占位
152. template<class T>
153. void AVLTree<T>::_cengci_travel(AVLNode<T> * cur){
154.         if(NULL == cur)
155.                 return;
156.         queue<AVLNode<T>*> q;
157.         q.push(cur);
158.         AVLNode<T> *top = NULL;
159.         queue<AVLNode<T>*> tmp;
160.        
161.         while(!q.empty()){
162.                 while(!q.empty()){
163.                         top = q.front();
164.                         q.pop();
165.                         if(NULL == top){
166.                                 //用#代表该节点是空，#的后代还是#
167.                                 cout << '#' << " ";
168.                                 tmp.push(top);
169.                         }else{
170.                                 cout << top->data.data << " ";
171.                                 tmp.push(top->son[0]);
172.                                 tmp.push(top->son[1]);
173.                         }
174.                 }
175.                 bool flag = false;
176.                 while(!tmp.empty()){
177.                         if(NULL != tmp.front())
178.                                 flag = true;
179.                         q.push(tmp.front());
180.                         tmp.pop();
181.                 }
182.                 cout << endl;
183.                 if(!flag)
184.                         break;
185.         }
186. }
187.  
188. //单旋转，即只旋转一次
189. //dir = 0时,左左旋转；否则为右右旋转
190. template<class T>
191. void AVLTree<T>::_singleRoate(AVLNode<T> *& cur, int dir){
192.         AVLNode<T> *& k2 = cur, * k1 = k2->son[dir];    //k2 必须是引用
193.         k2->son[dir] = k1->son[!dir];
194.         k1->son[!dir] = k2;
195.         k2 = k1;
196.        
197.         k2->setHeight();
198.         k1->setHeight();
199. }
200. //双旋转，即调两次单旋转
201. //dir = 0是左右情况； 否则为右左情况
202. template<class T>
203. void AVLTree<T>::_doubleRoate(AVLNode<T> *& cur, int dir){
204.         _singleRoate(cur->son[dir], !dir);
205.         _singleRoate(cur, dir);
206. }
207.  
208. /*************  公有方法（接口）开始**********************/
209. template<class T>
210. void AVLTree<T>::insert(const T & data){
211.         _insert(root, data);
212. }
213. template<class T>
214. void AVLTree<T>::mid_travel(){
215.         _mid_travel(root);
216. }
217.  
218. int main(){
219.         AVLTree<DNode>* avlt = new AVLTree<DNode>();
220.         const int num = 30;
221.         for(int i = 0; i < num; i++){
222.                 DNode * d = new DNode(i);
223.                 avlt->insert(*d);
224.  
225.         }
226.         cout << "*************中序遍历***************" << endl;
227.         avlt->mid_travel();
228.         cout << "**************中序遍历结束**********" << endl;
229.  
230.         cout << "*************层次遍历开始***************" << endl;
231.         avlt->cengci_travel();
232.         cout << "**************层次遍历结束**********" << endl;
233.         cout << "树的高度是： " << avlt->height() << endl;
234.         return 0;
235. }