【算法】二叉树的层次遍历

0x55AA

问题：
如何实现二叉树的层次遍历？
解析：
我们可以使用队列来解决这个问题
<1>将根节点压入队列
<2>判断队列是否为空
<3>不为空则获取队列最前端的元素，打印出该元素
<4>将该元素移除队列
<5>如果该元素有左孩子，则将其左孩子进入队列
<6>如果该元素有右孩子，则将其右孩子进入队列
主要函数如下所示：

1. template<typename Type> void BSTrees<Type>::traverseLevel(Node* root)
   
2. {
   
3.         if( root == NULL)
   
4.         {
   
5.                 cout<<"This is a empty tree"<<endl;
   
6.                 return;
   
7.         }
   
8.         queue<Node*> que;
   
9.         que.push(root);
   
10.         while( !que.empty() )
    
11.         {
    
12.                 Node* ptr = que.front();
    
13.                 que.pop();
    
14.                 cout<<ptr->e<<endl;
    
15.                 if(ptr->leftChild != NULL)
    
16.                         que.push(ptr->leftChild);
    
17.                 if(ptr->rightChild != NULL)
    
18.                         que.push(ptr->rightChild);
    
19.         }
    
20. }

复制代码

整个程序如下所示：
BSTrees.h

1. //BSTrees.h
   
2. #ifndef DDXX_BSTREES_H
   
3. #define DDXX_BSTREES_H
   
4. #include <iostream>
   
5. #include <queue>
   
6. using namespace std;
   
7. template<typename Type>
   
8. class BSTrees
   
9. {
   
10. public:
    
11.         BSTrees();
    
12.         ~BSTrees();
    
13. public:
    
14.         struct Node
    
15.         {
    
16.                 Type    e;
    
17.                 Node*   leftChild;
    
18.                 Node*   rightChild;
    
19.                 Node()
    
20.                 {
    
21.                 }
    
22.                 Node(Type _e)
    
23.                 {
    
24.                         e           = _e;
    
25.                         leftChild   = NULL;
    
26.                         rightChild  = NULL;
    
27.                 }
    
28.         };
    
29. public:
    
30.         bool    insert(Type e);
    
31.         bool    erase1(Type e);
    
32.         bool    erase2(Type e);
    
33.         void    clear();
    
34.         bool    isEmpty();
    
35.         int     getLength();
    
36.         Node*   find(Type e);
    
37.         Node*   getRoot();
    
38.         Node*   getParent(Node* p);
    
39.         void    traverse(Node* ptr);
    
40.         void    traverseLevel(Node* ptr);
    
41. private:
    
42.         void    clears(Node* &p);
    
43. private:
    
44.         Node*   m_root;
    
45.         int     m_Length;
    
46. };
    
47. 
    
48. template<typename Type> BSTrees<Type>::BSTrees()
    
49. {
    
50.         m_root = NULL;
    
51.         m_Length = 0;
    
52. }
    
53. 
    
54. template<typename Type> bool BSTrees<Type>::insert(Type e)
    
55. {
    
56.         Node* ptr = new Node(e);
    
57.         if ( ptr == NULL )
    
58.         {
    
59.                 cout<<"Allocate memory for the element failed"<<endl;
    
60.                 return false;
    
61.         }
    
62. 
    
63.         if( m_root == NULL)
    
64.         {
    
65.                 m_root = ptr;
    
66.                 m_Length++;
    
67.                 return true;
    
68.         }
    
69. 
    
70.         Node* p         = m_root;
    
71.         Node* pParent   = m_root;
    
72.         while( p != NULL)
    
73.         {
    
74.                 if( e == p->e)
    
75.                 {
    
76.                         cout<<"the element is already exist"<<endl;
    
77.                         delete ptr;
    
78.                         ptr = NULL;
    
79.                         return false;
    
80.                 }
    
81. 
    
82.                 pParent = p;
    
83.                 if( e > p->e)
    
84.                 {
    
85.                         p = p->rightChild;
    
86.                 }
    
87.                 else
    
88.                 {
    
89.                         p = p->leftChild;
    
90.                 }
    
91.         }
    
92. 
    
93.         if( e < pParent->e )
    
94.         {
    
95.                 pParent->leftChild = ptr;
    
96.         }
    
97.         if( e > pParent->e)
    
98.         {
    
99.                 pParent->rightChild = ptr;
    
100.         }
     
101. 
     
102.         m_Length++;
     
103.         return true;
     
104. }
     
105. 
     
106. template<typename Type> bool BSTrees<Type>::erase1(Type e)
     
107. {
     
108.         Node *p = find(e);
     
109.         if ( p == NULL )
     
110.         {
     
111.                 cout<<"There's no this element to delete"<<endl;
     
112.                 return false;
     
113.         }
     
114. 
     
115.         if ( p->leftChild == NULL)
     
116.         {
     
117.                 Node* pParent = getParent(p);
     
118.                 if( pParent->leftChild == p )
     
119.                         pParent->leftChild = p->rightChild;
     
120.                 else
     
121.                         pParent->rightChild = p->rightChild;
     
122.                 delete p;
     
123.                 p = NULL;
     
124. 
     
125.                 m_Length--;
     
126.                 return true;
     
127.         }
     
128. 
     
129.         if ( p->rightChild == NULL)
     
130.         {
     
131.                 Node* pParent = getParent(p);
     
132.                 if( pParent->leftChild == p)
     
133.                         pParent->leftChild = p->leftChild;
     
134.                 else
     
135.                         pParent->rightChild = p->leftChild;
     
136.                 delete p;
     
137.                 p = NULL;
     
138. 
     
139.                 m_Length--;
     
140.                 return true;
     
141.         }
     
142. 
     
143.         if ( p->leftChild != NULL && p->rightChild != NULL)
     
144.         {
     
145.                 Node* pParent = getParent(p);
     
146.                 Node* pPre = p->leftChild;
     
147.                 Node* ptmp = pPre;
     
148.                 while( pPre->rightChild != NULL )
     
149.                 {
     
150.                         ptmp = pPre;
     
151.                         pPre = pPre->rightChild;
     
152.                 }
     
153.                 if( ptmp != pPre)
     
154.                 {   ptmp->rightChild = pPre->leftChild;
     
155.                         pPre->leftChild = p->leftChild;
     
156.                         pPre->rightChild = p->rightChild;
     
157.                 }
     
158.                 else
     
159.                         pPre->rightChild = p->rightChild;
     
160. 
     
161.                 if( pParent == NULL )
     
162.                         m_root = pPre;
     
163.                 else
     
164.                         if( pParent->leftChild == p)
     
165.                                 pParent->leftChild = pPre;
     
166.                         else
     
167.                                 pParent->rightChild = pPre;
     
168. 
     
169.                 delete p;
     
170.                 p = NULL;
     
171. 
     
172.                 m_Length--;
     
173.                 return true;
     
174.         }
     
175. 
     
176. }
     
177. 
     
178. template<typename Type> bool  BSTrees<Type>::erase2(Type e)
     
179. {
     
180.         Node *p = find(e);
     
181.         if ( p == NULL )
     
182.         {
     
183.                 cout<<"There's no this element to delete"<<endl;
     
184.                 return false;
     
185.         }
     
186. 
     
187.         if ( p->leftChild == NULL)
     
188.         {
     
189.                 Node* pParent = getParent(p);
     
190.                 if( pParent->leftChild == p )
     
191.                         pParent->leftChild = p->rightChild;
     
192.                 else
     
193.                         pParent->rightChild = p->rightChild;
     
194.                 delete p;
     
195.                 p = NULL;
     
196. 
     
197.                 m_Length--;
     
198.                 return true;
     
199.         }
     
200. 
     
201.         if ( p->rightChild == NULL)
     
202.         {
     
203.                 Node* pParent = getParent(p);
     
204.                 if( pParent->leftChild == p)
     
205.                         pParent->leftChild = p->leftChild;
     
206.                 else
     
207.                         pParent->rightChild = p->leftChild;
     
208.                 delete p;
     
209.                 p = NULL;
     
210. 
     
211.                 m_Length--;
     
212.                 return true;
     
213.         }
     
214.         if( p->leftChild != NULL && p->rightChild != NULL)
     
215.         {
     
216.                 Node* pParent = getParent(p);
     
217.                 Node* ptr = p->leftChild;
     
218.                 while( ptr->rightChild != NULL )
     
219.                         ptr = ptr->rightChild;
     
220.                 ptr->rightChild = p->rightChild;
     
221. 
     
222.                 if( pParent == NULL )
     
223.                         m_root = p->leftChild;
     
224.                 else
     
225.                         if(pParent->leftChild == p)
     
226.                                 pParent->leftChild = p->leftChild;
     
227.                         else
     
228.                                 pParent->rightChild = p->leftChild;
     
229.                 delete p;
     
230.                 p = NULL;
     
231.                 m_Length--;
     
232.                 return true;
     
233.         }
     
234. }
     
235. 
     
236. template<typename Type> void  BSTrees<Type>::clear()
     
237. {
     
238.         if( m_root == NULL )
     
239.                 return;
     
240.         clears(m_root);
     
241.         m_root = NULL;
     
242. }
     
243. 
     
244. template<typename Type> void   BSTrees<Type>::clears(Node* &p)
     
245. {
     
246.         if(p->leftChild != NULL)
     
247.         {
     
248.                 clears(p->leftChild);
     
249.                 p->leftChild = NULL;
     
250.         }
     
251.         if(p->rightChild != NULL)
     
252.         {
     
253.                 clears(p->rightChild);
     
254.                 p->rightChild = NULL;
     
255.         }
     
256.         delete p;
     
257.         p = NULL;
     
258.         m_Length--;
     
259. 
     
260. }
     
261. template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::getRoot()
     
262. {
     
263.         return m_root;
     
264. }
     
265. template<typename Type> int       BSTrees<Type>::getLength()
     
266. {
     
267.         return m_Length;
     
268. }
     
269. template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::getParent(Node* p)
     
270. {
     
271.         if( p == m_root)
     
272.                 return NULL;
     
273.         Node* ptr = m_root;
     
274.         Node* ptf = ptr;
     
275.         while( ptr != NULL )
     
276.         {
     
277.                 if ( ptr->e == p->e )
     
278.                         return ptf;
     
279.                 if ( ptr->e > p->e )
     
280.                 {
     
281.                         ptf = ptr;
     
282.                         ptr = ptr->leftChild;
     
283.                 }
     
284.                 else
     
285.                 {
     
286.                         ptf = ptr;
     
287.                         ptr = ptr->rightChild;
     
288.                 }
     
289.         }
     
290. 
     
291. }
     
292. 
     
293. template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::find(Type e)
     
294. {
     
295.         Node* ptr = m_root;
     
296. 
     
297.         while(ptr != NULL)
     
298.         {
     
299.                 if ( ptr->e == e )
     
300.                         return ptr;
     
301.                 if ( ptr->e > e )
     
302.                         ptr = ptr->leftChild;
     
303.                 else
     
304.                         ptr = ptr->rightChild;
     
305.         }
     
306.         //if ( ptr == NULL )
     
307.         return NULL;
     
308. }
     
309. 
     
310. template<typename Type> void BSTrees<Type>::traverse(Node* ptr)
     
311. {
     
312.         if( ptr == NULL )
     
313.                 return;
     
314.         if( ptr->leftChild != NULL )
     
315.                 traverse(ptr->leftChild);
     
316.         cout<<"Element value:"<<ptr->e<<endl;
     
317.         if( ptr->rightChild != NULL )
     
318.                 traverse(ptr->rightChild);
     
319. }
     
320. 
     
321. template<typename Type> void BSTrees<Type>::traverseLevel(Node* root)
     
322. {
     
323.         if( root == NULL)
     
324.         {
     
325.                 cout<<"This is a empty tree"<<endl;
     
326.                 return;
     
327.         }
     
328.         queue<Node*> que;
     
329.         que.push(root);
     
330.         while( !que.empty() )
     
331.         {
     
332.                 Node* ptr = que.front();
     
333.                 que.pop();
     
334.                 cout<<ptr->e<<endl;
     
335.                 if(ptr->leftChild != NULL)
     
336.                         que.push(ptr->leftChild);
     
337.                 if(ptr->rightChild != NULL)
     
338.                         que.push(ptr->rightChild);
     
339.         }
     
340. }
     
341. template<typename Type> BSTrees<Type>::~BSTrees()
     
342. {
     
343.         clear();
     
344. }
     
345. #endif

复制代码

main.cpp

1. //main.cpp
   
2. #include <iostream>
   
3. #include "BST.h"
   
4. using namespace std;
   
5. 
   
6. 
   
7. void main()
   
8. {
   
9.         BSTrees<int>Bst;
   
10.         int Arr[9] = {6,2,8,4,10,0,12,16,14};
    
11.         for (int i=0;i<9;i++)
    
12.                 Bst.insert(Arr[i]);
    
13.         Bst.traverse(Bst.getRoot());
    
14.         cout<<"Tree'slength is:"<<Bst.getLength()<<endl;
    
15.         Bst.traverseLevel(Bst.getRoot());
    
16. }

复制代码