非递归实现二叉树的遍历

1、先序遍历

基本思想：

1>首先定义一个栈，每遇到一个节点，就对其数据进行访问；然后将其入栈，将当前节点的左孩子赋给它，循环此过程，直到最左节点被访问并被压入栈中。

2>出循环后用临时变量保存栈顶节点，然后对栈顶节点进行出栈操作，到此说明当前节点以及其左子树已被访问过了。

3>将临时变量的右孩子赋给当前节点，用子问题的方式去访问其右子树。

[cpp] view plain copy print?

1. void preorderR(Node* root)//先序遍历打印树的各个节点  
2.     {  
3.         Node* cur = root;  
4.         stack<Node*> s;  
5.         while (!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完  
6.         {  
7.             while(cur)//先序遍历，遇到树根节点直接访问数据并将其压栈  
8.             {  
9.                 cout<<cur->_value<<" ";  
10.                 s.push(cur);  
11.                 cur = cur->_lchild;  
12.             }  
13.   
14.             Node* top = s.top();//取出栈顶元素，到此说明此节点以及其左子树已经访问过了  
15.             s.pop();  
16.   
17.             cur = top->_rchild;//以子问题的方式去访问右子树  
18.         }  
19.         cout<<endl;  
20.     }  

2、中序遍历

基本思想：

1>首先定义一个栈，每遇到一个节点，就将其入栈，将当前节点的左孩子赋给它，循环此过程，直到最左节点将其压入栈中。

2>出循环后用临时变量保存栈顶节点，访问栈顶节点的数据，然后对栈顶节点进行出栈操作，到此说明当前节点的左子树以及当前节点已被访问过了。

3>将临时变量的右孩子赋给当前节点，用子问题的方式去访问其右子树。

[cpp] view plain copy print?

1. void inorderR(Node* root)//中序遍历打印树的各个节点  
2. {  
3.     Node* cur = root;  
4.     stack<Node*> s;  
5.     while(!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完  
6.     {  
7.         while(cur)//中序遍历，遇到树根节点直接将其压栈  
8.         {  
9.             s.push(cur);  
10.             cur = cur->_lchild;  
11.         }  
12.   
13.         Node* top = s.top();//取出栈顶元素，到此说明此节点的左子树已经访问过了  
14.         cout<<top->_value<<" ";//访问栈顶元素（即根节点）  
15.         s.pop();  
16.   
17.         cur = top->_rchild;//以子问题的方式去访问右子树  
18.     }  
19.     cout<<endl;  
20. }  

3、后序遍历

1>首先定义一个栈和一个记录上一个被访问节点的变量，每遇到一个节点，就对其数据进行访问；然后将其入栈，将当前节点的左孩子赋给它，循环此过程，直到最左节点被访问并被压入栈中。

2>出循环后用临时变量保存栈顶元素，只有当前节点的右子树为空或者其右子树已经访问过时，才能对当前节点进行访问，同时将栈顶元素出栈

3>将临时变量的右孩子赋给当前节点，用子问题的方式去访问其右子树。

[cpp] view plain copy print?

1. void postorderR(Node* root)//后序遍历打印树的各个节点  
2.     {  
3.         Node* cur = root;  
4.         Node* prev = NULL;//上一个访问过的数据  
5.         stack<Node*> s;  
6.         while(!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完  
7.         {  
8.             //后序遍历，遇到树根节点直接将其压栈  
9.             while(cur)  
10.             {  
11.                 s.push(cur);  
12.                 cur = cur->_lchild;  
13.             }  
14.   
15.             Node* top = s.top();//取栈顶元素，但不一定能访问  
16.               
17.             //当节点右子树为空或已经访问过时对其直接进行访问  
18.             if (top->_rchild==NULL || top->_rchild==prev)  
19.             {  
20.                 cout<<top->_value<<" ";  
21.                 prev = top;//将prev更新为已经访问的节点  
22.                 s.pop();  
23.             }  
24.             else//以子问题的方式去访问右子树  
25.             {  
26.                 cur = top->_rchild;  
27.             }  
28.        }  
29.         cout<<endl;  
30.     }  

完整的代码及测试：

[cpp] view plain copy print?

1. #include <iostream>  
2. #include <cassert>  
3. #include <queue>  
4. #include <stack>  
5. using namespace std;  
6.   
7. template <class T>  
8. struct TreeNode  
9. {  
10.     TreeNode(const T& value = T())  
11.         :_value(value)  
12.         ,_lchild(0)  
13.         ,_rchild(0)  
14.     {}  
15.     T _value;//节点的值  
16.     TreeNode<T>* _lchild;//左孩子  
17.     TreeNode<T>* _rchild;//右孩子  
18. };  
19.   
20. template <class T>  
21. class BinaryTree  
22. {  
23. public:  
24.     typedef TreeNode<T> Node;  
25.     BinaryTree()//无参构造函数  
26.         :_root(NULL)  
27.     {}  
28.     BinaryTree(const T* a,size_t size,const T& invalid)//构造函数  
29.     {  
30.         assert(a);  
31.         size_t index = 0;  
32.         _root = CreatTree(a,size,invalid,index);  
33.     }  
34.     BinaryTree(const BinaryTree<T>& b)//拷贝构造  
35.     {  
36.         _root = Copy(b._root);  
37.     }  
38.     //现代写法的赋值运算符重载1  
39.     BinaryTree& operator=(const BinaryTree<T>& b)  
40.     {  
41.         if (this != &b)  
42.         {  
43.             Node* tmp = Copy(b._root);  
44.             Destroy(_root) ;  
45.             _root = tmp;  
46.             //swap(_root,tmp);  
47.         }  
48.         return *this;  
49.     }  
50.     ////现代写法的赋值运算符重载2  
51.     //BinaryTree& operator=(BinaryTree<T> b)  
52.     //{  
53.     //  swap(b._root,_root);  
54.     //  return *this;  
55.     //}  
56.     ~BinaryTree()//析构  
57.     {  
58.         if (NULL != _root)  
59.         {  
60.             Destroy(_root);  
61.             _root = NULL;  
62.         }  
63.     }  
64.     void PreOrder()//先序遍历打印树的各个节点  
65.     {  
66.         cout<<"先序遍历:";  
67.         preorderR(_root);  
68.         cout<<endl;  
69.     }  
70.     void InOrder()//中序遍历打印树的各个节点  
71.     {  
72.         cout<<"中序遍历:";  
73.         inorderR(_root);  
74.         cout<<endl;  
75.     }  
76.     void PostOrder()//后序遍历打印树的各个节点  
77.     {  
78.         cout<<"后序遍历:";  
79.         postorderR(_root);  
80.         cout<<endl;  
81.     }  
82.     void LevelOrder()//层序遍历打印树的各个节点  
83.     {  
84.         cout<<"层序遍历:";  
85.         levelorder(_root);  
86.         cout<<endl;  
87.     }  
88.     size_t Size()//求树中的节点个数  
89.     {  
90.         cout<<"size:";  
91.         return size(_root);  
92.     }  
93.     size_t Depth()//求树的深度  
94.     {  
95.         cout<<"depth:";  
96.         return depth(_root);  
97.     }  
98.     size_t GetLeafSize()  
99.     {  
100.         cout<<"leaf_size:";  
101.         return getleafsize(_root);  
102.     }  
103.     size_t GetKLevelSize(size_t k)//树中第k层的节点个数  
104.     {  
105.         cout<<k<<"_level_size:";  
106.         return getklevelsize(_root,k);  
107.     }  
108. protected:  
109.     //按照先序遍历递归建树  
110.     Node* CreatTree(const T* a,size_t size,const T& invalid,size_t& index)//注意index的传值方式  
111.     {  
112.         assert(a);  
113.         Node* root = NULL;  
114.         if (a[index] != invalid && index < size)//按先序遍历建树  
115.         {  
116.             root = new Node(a[index]);  
117.             root->_lchild = CreatTree(a,size,invalid,++index);  
118.             root->_rchild = CreatTree(a,size,invalid,++index);  
119.         }  
120.         return root;  
121.     }  
122.     //拷贝对象  
123.     Node* Copy(Node* root)  
124.     {  
125.         Node* tmp = NULL;  
126.   
127.         if(root)  
128.         {  
129.             tmp = new Node(root->_value);  
130.             tmp->_lchild = Copy(root->_lchild);  
131.             tmp->_rchild = Copy(root->_rchild);  
132.         }  
133.         return tmp;  
134.     }  
135.     //释放空间  
136.     void Destroy(Node*& root)  
137.     {  
138.         if(root)//用后序遍历方式释放空间  
139.         {  
140.             Destroy(root->_rchild);  
141.             Destroy(root->_lchild);  
142.             delete root;  
143.             root = NULL;  
144.         }  
145.     }  
146.     void preorderR(Node* root)//先序遍历打印树的各个节点  
147.     {  
148.         Node* cur = root;  
149.         stack<Node*> s;  
150.         while (!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完  
151.         {  
152.             while(cur)//先序遍历，遇到树根节点直接访问数据并将其压栈  
153.             {  
154.                 cout<<cur->_value<<" ";  
155.                 s.push(cur);  
156.                 cur = cur->_lchild;  
157.             }  
158.   
159.             Node* top = s.top();//取出栈顶元素，到此说明此节点以及其左子树已经访问过了  
160.             s.pop();  
161.   
162.             cur = top->_rchild;//以子问题的方式去访问右子树  
163.         }  
164.         cout<<endl;  
165.     }  
166.     void inorderR(Node* root)//中序遍历打印树的各个节点  
167.     {  
168.         Node* cur = root;  
169.         stack<Node*> s;  
170.         while(!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完  
171.         {  
172.             while(cur)//中序遍历，遇到树根节点直接将其压栈  
173.             {  
174.                 s.push(cur);  
175.                 cur = cur->_lchild;  
176.             }  
177.   
178.             Node* top = s.top();//取出栈顶元素，到此说明此节点的左子树已经访问过了  
179.             cout<<top->_value<<" ";//访问栈顶元素（即根节点）  
180.             s.pop();  
181.   
182.             cur = top->_rchild;//以子问题的方式去访问右子树  
183.         }  
184.         cout<<endl;  
185.     }  
186.     void postorderR(Node* root)//后序遍历打印树的各个节点  
187.     {  
188.         Node* cur = root;  
189.         Node* prev = NULL;//上一个访问过的数据  
190.         stack<Node*> s;  
191.         while(!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完  
192.         {  
193.             //后序遍历，遇到树根节点直接将其压栈  
194.             while(cur)  
195.             {  
196.                 s.push(cur);  
197.                 cur = cur->_lchild;  
198.             }  
199.   
200.             Node* top = s.top();//取栈顶元素，但不一定能访问  
201.               
202.             //当节点右子树为空或已经访问过时对其直接进行访问  
203.             if (top->_rchild==NULL || top->_rchild==prev)  
204.             {  
205.                 cout<<top->_value<<" ";  
206.                 prev = top;//将prev更新为已经访问的节点  
207.                 s.pop();  
208.             }  
209.             else//以子问题的方式去访问右子树  
210.             {  
211.                 cur = top->_rchild;  
212.             }  
213.        }  
214.         cout<<endl;  
215.     }  
216.       
217.     void levelorder(Node* root)//层序遍历打印树的各个节点  
218.     {  
219.         queue<Node*> q;  
220.         if (root)  
221.         {  
222.             q.push(root);//将根节点插进队列  
223.         }  
224.         while(!q.empty())  
225.         {  
226.             Node* front = q.front();  
227.             q.pop();  
228.             cout<<front->_value<<" ";  
229.             if (front->_lchild)  
230.             {  
231.                 q.push(front->_lchild);  
232.             }  
233.             if (front->_rchild)  
234.             {  
235.                 q.push(front->_rchild);  
236.             }  
237.         }  
238.     }  
239.     size_t size(Node* root)//求树中的节点个数  
240.     {  
241.         size_t count = 0;  
242.         if (NULL == root)  
243.         {  
244.             count = 0;  
245.         }  
246.         else  
247.         {  
248.             //当前节点 = 左子树节点 + 右子树节点 + 1  
249.             count = size(root->_lchild) + size(root->_rchild)+ 1;  
250.         }  
251.         return count;  
252.     }  
253.     size_t depth(Node* root)//求树的深度  
254.     {  
255.         if (NULL == root)  
256.         {  
257.             return 0;  
258.         }  
259.         else  
260.         {  
261.             return depth(root->_lchild)>depth(root->_rchild)?  
262.                 (depth(root->_lchild)+1):(depth(root->_rchild)+1);  
263.         }  
264.     }  
265.     size_t getleafsize(Node* root)//求叶节点的个数  
266.     {  
267.         if (NULL == root)//空树  
268.         {  
269.             return 0;  
270.         }  
271.         if (NULL == root->_lchild && NULL == root->_rchild)//左叶节点右节点均为空，即  
272.         {  
273.             return 1;  
274.         }  
275.         else//左子树的叶节点+右子树的叶节点  
276.         {  
277.             return getleafsize(root->_lchild)+getleafsize(root->_rchild);  
278.         }  
279.     }  
280.     size_t getklevelsize(Node* root,size_t k)//树中第k层的节点个数  
281.     {  
282.         assert(k>0);  
283.   
284.         size_t count = 0;  
285.         if (NULL == root)  
286.         {  
287.             return 0;  
288.         }  
289.         if (k == 1)  
290.         {  
291.             count++;  
292.         }  
293.         else  
294.         {  
295.             count =  getklevelsize(root->_lchild,k-1)  
296.                 + getklevelsize(root->_rchild,k-1);  
297.         }  
298.         return count;  
299.     }  
300. protected:  
301.     Node* _root;//根节点  
302. };  
303.   
304. void TestBinaryTree()  
305. {  
306.     int arr[] = {1, 2, 3, '#', '#', 4, '#' , '#', 5, 6,'#','#','#'};  
307.     size_t size = sizeof(arr)/sizeof(arr[0]);  
308.     BinaryTree<int> bt(arr,size,'#');  
309.     BinaryTree<int> b1(bt);  
310.     BinaryTree<int> b2;  
311.     b2 = bt;  
312.     b2.PreOrder();  
313.     b2.InOrder();  
314.     b2.PostOrder();  
315.     b2.LevelOrder();  
316.     cout<<b2.Size()<<endl;  
317.     cout<<b2.Depth()<<endl;  
318.     cout<<b2.GetLeafSize()<<endl;  
319.     cout<<b2.GetKLevelSize(1)<<endl;  
320.     cout<<b2.GetKLevelSize(2)<<endl;  
321.     cout<<b2.GetKLevelSize(3)<<endl;  
322. }  
323.   
324. int main()  
325. {  
326.     TestBinaryTree();  
327.     system("pause");  
328.     return 0;  
329. }