小甲鱼来看看AVL树的问题

柠“萌”圆

我按你的教程敲的代码(虽然是C++的),测试正常,不过我前序遍历树时,根据遍历结果画出来的树不是AVL树,求解决

1. #ifndef AVL_H_INCLUDED
   
2. #define AVL_H_INCLUDED
   
3. 
   
4. #include <memory>
   
5. #include <initializer_list>
   
6. #include <iostream>
   
7. 
   
8. 
   
9. template <class Type>
   
10. class AVL{
    
11.     enum BF{RH = -1, EH, LH};
    
12. 
    
13.     struct BiTreeNode {
    
14.         Type _data;
    
15.         BF _bf;
    
16.         std::shared_ptr<BiTreeNode> _lChild;
    
17.         std::shared_ptr<BiTreeNode> _rChild;
    
18.     };
    
19. 
    
20.     typedef std::shared_ptr<BiTreeNode> Tree;
    
21. 
    
22. public:
    
23.     typedef size_t size_type;
    
24.     typedef Type value_type;
    
25.     typedef value_type& reference;
    
26.     typedef const reference const_reference;
    
27. 
    
28.     AVL(const AVL<Type>&) = delete;
    
29.     AVL<Type>& operator=(const AVL<Type>&) = delete;
    
30. 
    
31.     AVL() = default;
    
32.     AVL(const std::initializer_list<Type>& li) : AVL(li.begin(), li.end()) {}
    
33.     template <class In> AVL(In first, In last);
    
34. 
    
35.     AVL<Type>& push(const Type&);
    
36. //    AVL<Type>& pop(const Type&);
    
37.     bool find(const Type&)const;
    
38.     size_type size()const { return _size; }
    
39.     bool empty()const { return _size == 0; }
    
40.     const_reference root() const { return _root ->_data; }
    
41.     void show()const { show(_root); }
    
42. 
    
43. private:
    
44.     bool push(Tree& root, const Type&, bool& taller);
    
45.     void left_balance(Tree& root);
    
46.     void left_rotate(Tree& root); // 左旋操作
    
47.     void right_balance(Tree& root);
    
48.     void right_rotate(Tree& root); // 右旋操作
    
49.     bool find(const Tree&, const Type&)const;
    
50.     void show(const Tree&)const;
    
51. 
    
52.     Tree _root;
    
53.     size_type _size = 0;
    
54. };
    
55. 
    
56. template <class Type>
    
57. bool AVL<Type>::push(Tree& root, const Type& item, bool& taller)
    
58. {
    
59.     if (!root) {
    
60.         root = std::make_shared<BiTreeNode>();
    
61.         root ->_bf = EH;
    
62.         root ->_data = item;
    
63.         taller = true;
    
64.         ++_size;
    
65.     }
    
66.     else if (item == root ->_data)
    
67.         return taller = false;
    
68.     else if (item < root ->_data) {
    
69. 
    
70.         if (!push(root ->_lChild, item, taller))
    
71.             return false;
    
72. 
    
73.         if (taller) { // 树的高度增加了
    
74.             switch (root ->_bf) {
    
75. 
    
76.             case LH: // 未插入时左子树比右子树高
    
77.                      // 形成不平衡局面
    
78.                 left_balance(root); // 调整
    
79.                 taller = false; // 平衡后树的高度不增加
    
80.                 break;
    
81. 
    
82.             case EH: // 未插入时树左右一样高
    
83.                 root ->_bf = LH; // 插入后左子树比右子树高
    
84.                 taller = true; // 树的高度增加了
    
85.                 break;
    
86. 
    
87.             case RH: // 未插入时右子树高
    
88.                 root ->_bf = EH; // 插入后左右子树一样高
    
89.                 taller = false; // 树的高度未增加
    
90.                 break;
    
91.             }
    
92.         }
    
93.         else { // 没有成功地插入左子树
    
94. 
    
95.             if (!push(root ->_rChild, item, taller))
    
96.                 return false;
    
97. 
    
98.             if (taller) {
    
99.                 switch (root ->_bf) {
    
100. 
     
101.                 case LH:
     
102.                     root ->_bf = EH;
     
103.                     taller = false;
     
104.                     break;
     
105. 
     
106.                 case EH:
     
107.                     root ->_bf = RH;
     
108.                     taller = true;
     
109.                     break;
     
110. 
     
111.                 case RH:
     
112.                     right_balance(root);
     
113.                     taller = false;
     
114.                     break;
     
115.                 }
     
116.             }
     
117.         }
     
118.     }
     
119.     else {
     
120.         if (!push(root ->_rChild, item, taller))
     
121.             return false;
     
122. 
     
123.         if (taller) {
     
124.             switch (root ->_bf) {
     
125. 
     
126.             case LH:
     
127.                 root ->_bf = EH;
     
128.                 taller = false;
     
129.                 break;
     
130. 
     
131.             case EH:
     
132.                 root ->_bf = RH;
     
133.                 taller = true;
     
134.                 break;
     
135. 
     
136.                 case RH:
     
137.                 right_balance(root);
     
138.                 taller = false;
     
139.                 break;
     
140.                 }
     
141.             }
     
142.         else {
     
143.         if (!push(root ->_lChild, item, taller))
     
144.             return false;
     
145. 
     
146.         if (taller) {
     
147.             switch (root ->_bf) {
     
148. 
     
149.             case LH:
     
150. 
     
151.                 left_balance(root);
     
152.                 taller = false;
     
153.                 break;
     
154. 
     
155.             case EH:
     
156.                 root ->_bf = LH;
     
157.                 taller = true;
     
158.                 break;
     
159. 
     
160.             case RH:
     
161.                 root ->_bf = EH;
     
162.                 taller = false;
     
163.                 break;
     
164.                 }
     
165.             }
     
166.         }
     
167.     }
     
168.     return false;
     
169. }
     
170. 
     
171. template <class Type>
     
172. void AVL<Type>::left_balance(Tree& root)
     
173. {
     
174.     Tree l = root ->_lChild, lr;
     
175. 
     
176.     switch (l ->_bf) {
     
177. 
     
178.     case LH: // 若左子树比右子树高
     
179.         root ->_bf = l ->_bf = EH;
     
180.         right_rotate(root); // 右旋
     
181.         break;
     
182. 
     
183.     case RH:
     
184.         lr = l ->_rChild;
     
185. 
     
186.         switch (lr ->_bf) {
     
187. 
     
188.         case LH:
     
189.             root ->_bf = RH;
     
190.             l ->_bf = EH;
     
191.             break;
     
192. 
     
193.         case EH:
     
194.             root ->_bf = l ->_bf = EH;
     
195.             break;
     
196. 
     
197.         case RH:
     
198.             root ->_bf = EH;
     
199.             l ->_bf = LH;
     
200.             break;
     
201.         }
     
202.         lr ->_bf = EH;
     
203.         left_rotate(root ->_lChild); // 双旋处理
     
204.         right_rotate(root);
     
205. 
     
206.         break;
     
207.     }
     
208. }
     
209. 
     
210. template <class Type>
     
211. void AVL<Type>::right_rotate(Tree& root)
     
212. {
     
213.     Tree l = root ->_lChild;
     
214. 
     
215.     root ->_lChild = l ->_rChild;
     
216.     l ->_rChild = root;
     
217.     root = l;
     
218. }
     
219. 
     
220. template <class Type>
     
221. void AVL<Type>::left_rotate(Tree& root)
     
222. {
     
223.     Tree r = root ->_rChild;
     
224. 
     
225.     root ->_rChild = r ->_lChild;
     
226.     r ->_lChild = root;
     
227.     root = r;
     
228. }
     
229. 
     
230. template <class Type>
     
231. void AVL<Type>::right_balance(Tree& root)
     
232. {
     
233.     Tree l = root ->_lChild, lr;
     
234. 
     
235.     switch (l ->_bf) {
     
236. 
     
237.     case RH:// 若右子树比左子树高
     
238.         root ->_bf = l ->_bf = EH;
     
239.         left_rotate(root);
     
240.         break;
     
241. 
     
242.     case LH:
     
243.         lr = l ->_rChild;
     
244. 
     
245.         switch (lr ->_bf) {
     
246. 
     
247.         case LH:
     
248.             root ->_bf = RH;
     
249.             l ->_bf = EH;
     
250.             break;
     
251. 
     
252.         case EH:
     
253.             root ->_bf = l ->_bf = EH;
     
254.             break;
     
255. 
     
256.         case RH:
     
257.             root ->_bf = EH;
     
258.             l ->_bf = LH;
     
259.             break;
     
260.         }
     
261.         lr ->_bf = EH;
     
262.         right_rotate(root ->_rChild); // 双旋处理
     
263.         left_rotate(root);
     
264. 
     
265.         break;
     
266.     }
     
267. }
     
268. 
     
269. template <class Type>
     
270. AVL<Type>& AVL<Type>::push(const Type& item)
     
271. {
     
272.     bool taller;
     
273.     push(_root, item, taller);
     
274.     return *this;
     
275. }
     
276. 
     
277. 
     
278. template <class Type>
     
279. template <class In>
     
280. AVL<Type>::AVL(In first, In last)
     
281. {
     
282.     while (first != last)
     
283.         push(*first++);
     
284. }
     
285. 
     
286. template <class Type>
     
287. bool AVL<Type>::find(const Type& item)const
     
288. {
     
289.     return find(_root, item);
     
290. }
     
291. 
     
292. template <class Type>
     
293. bool AVL<Type>::find(const Tree& root, const Type& item)const
     
294. {
     
295.     if (root) {
     
296.         if (root ->_data == item)
     
297.             return true;
     
298.         if (item < root ->_data)
     
299.             return find(root ->_lChild, item);
     
300.         else
     
301.             return find(root ->_rChild, item);
     
302.     }
     
303. 
     
304.     return false;
     
305. }
     
306. 
     
307. template <class Type>
     
308. void AVL<Type>::show(const Tree& root)const
     
309. {
     
310.     if (root) {
     
311.         std::cout << "root:\n";
     
312.         std::cout << root ->_data << '\n';
     
313. 
     
314. 
     
315.         std::cout << "lChild:\n";
     
316.         show(root ->_lChild);
     
317. 
     
318.         if (root == _root)
     
319.             std::cout << "真*根节点";
     
320. 
     
321.         std::cout << "rChild:\n";
     
322.         show(root ->_rChild);
     
323. 
     
324.         if (!root ->_lChild && !root ->_rChild)
     
325.             std::cout << "*************************\n";
     
326.     }
     
327. }
     
328. 
     
329. #endif // AVL_H_INCLUDED

复制代码

测试代码

1. #include "AVL.h"
   
2. #include <iostream>
   
3. 
   
4. int main()
   
5. {
   
6.     AVL<int> avl {5,7,8,9,3,0,1,2,4,1,5};
   
7. 
   
8.     std::cout << "size: " << avl.size() << "\nfind(5) = " << avl.find(5) << "\nfind(1) = " << avl.find(1)
   
9.     << "\nfind(8) = " << avl.find(8) << "\nfind(10) = " << avl.find(10) << "\nfind(0) = " << avl.find(0)
   
10.     << "\nfind(4) = " << avl.find(4) << "\nfind(3) = " << avl.find(3) << "\nfind(2) = " << avl.find(2) << "\nfind(7) = "
    
11.     << avl.find(7) << "\nfind(9) = " << avl.find(9) << "\n";
    
12.     avl.show();
    
13.     avl.push(10);
    
14.     std::cout << "\nfind(10) = " << avl.find(10) << "\n";
    
15.     return 0;
    
16. }

复制代码