二叉树的递归与非递归遍历

ypxing

看了版主converse写的二叉树的递归与非递归遍历

http://www.cppblog.com/converse/archive/2006/07/08/9577.html

其中, 版主写到:
"感觉其中后序遍历的非递归算法比较困难,想了很久最后的实现还是不够优雅"

俺也写了一个玩玩, 功能一样, 但是思路不一样, 呵呵

1. 
   
2. #include <iostream>
   
3. #include <stack>
   
4. #include <cassert>
   
5. using namespace std;
   
6. 
   
7. struct node
   
8. {
   
9.   node* lchild;
   
10.   node* rchild;
    
11.   int key;
    
12.   node(int data=0, node* left=NULL, node* right=NULL)
    
13.   {
    
14.     key = data;
    
15.     lchild = left;
    
16.     rchild = right;
    
17.   }
    
18. };
    
19. 
    
20. class Tree
    
21. {
    
22.   
    
23. public:
    
24.   Tree()
    
25.   {
    
26.     root = NULL;
    
27.   }
    
28.   Tree(int array[], int size);
    
29.   ~Tree();
    
30.   void traverse();
    
31.   void postTraverse();
    
32.   void recur_postTraverse(node* cur);
    
33.   void preTraverse();
    
34.   void recur_preTraverse(node* cur);
    
35.   void inTraverse();
    
36.   void recur_inTraverse(node* cur);
    
37. 
    
38. private:
    
39.   Tree(const Tree& t);
    
40.   Tree& operator=(const Tree& t);
    
41.   node* createTree(int array[], int size);
    
42.   void destroyTree(node* cur);
    
43. private:
    
44.   node* root;
    
45.   
    
46. };
    
47. 
    
48. Tree::Tree(int array[], int size)
    
49. {
    
50.   if ((array==NULL)||(size<=0))
    
51.     root = NULL;
    
52.   else
    
53.     root = createTree(array, size);
    
54. }
    
55. 
    
56. node* Tree::createTree(int array[], int size)
    
57. {
    
58.   if ((array==NULL)||(size<=0))
    
59.     return NULL;
    
60.   int mid=size/2;
    
61.   node* cur=new node(array[mid]);
    
62.   cur->lchild = createTree(array, mid);
    
63.   cur->rchild = createTree(array+mid+1, size-mid-1);
    
64.   return cur;
    
65. }
    
66. 
    
67. Tree::~Tree()
    
68. {
    
69.   destroyTree(root);
    
70. }
    
71. 
    
72. void Tree::destroyTree(node* cur)
    
73. {
    
74.   if (cur != NULL)
    
75.   {
    
76.     destroyTree(cur->lchild);
    
77.     destroyTree(cur->rchild);
    
78.     delete cur;
    
79.   }
    
80.   
    
81. }
    
82. 
    
83. 
    
84. //后序递归遍历
    
85. void Tree::recur_postTraverse(node* cur)
    
86. {
    
87.   if (cur!=NULL)
    
88.   {
    
89.     recur_postTraverse(cur->lchild);
    
90.     recur_postTraverse(cur->rchild);
    
91.     cout << cur->key << " ";
    
92.   }
    
93. }
    
94. 
    
95. //先序递归遍历
    
96. void Tree::recur_preTraverse(node* cur)
    
97. {
    
98.   if (cur!=NULL)
    
99.   {
    
100.     cout << cur->key << " ";
     
101.     recur_preTraverse(cur->lchild);
     
102.     recur_preTraverse(cur->rchild);
     
103.   }
     
104. }
     
105. 
     
106. //中序递归遍历
     
107. void Tree::recur_inTraverse(node* cur)
     
108. {
     
109.   if (cur!=NULL)
     
110.   {
     
111.     recur_inTraverse(cur->lchild);
     
112.     cout << cur->key << " ";
     
113.     recur_inTraverse(cur->rchild);
     
114.   }
     
115. }
     
116. 
     
117. //后序非递归遍历
     
118. void Tree::postTraverse()
     
119. {
     
120.   stack<node*> treeStack;
     
121.   node *pre, *cur;
     
122.   cur = root;
     
123.   pre = NULL;
     
124.   
     
125.   if (cur!=NULL)
     
126.     treeStack.push(cur);
     
127.   
     
128.   while(!treeStack.empty())
     
129.   {
     
130.     cur = treeStack.top();
     
131.     if (((cur->lchild==NULL)&&(cur->rchild==NULL))||             //没有孩子结点或者
     
132.         ((pre!=NULL)&&((pre==cur->lchild)||(pre==cur->rchild)))) //孩子遍历过了
     
133.     {
     
134.       treeStack.pop();
     
135.       cout << cur->key << " ";
     
136.       pre = cur;
     
137.     }
     
138.     else
     
139.     {
     
140.       if (cur->rchild!=NULL)
     
141.         treeStack.push(cur->rchild);
     
142.       if (cur->lchild!=NULL)
     
143.         treeStack.push(cur->lchild);
     
144.     }
     
145.    
     
146.   }
     
147.   
     
148. }
     
149. 
     
150. //中序非递归遍历
     
151. void Tree::inTraverse()
     
152. {
     
153.   stack<node*> treeStack;
     
154.   node *pre, *cur;
     
155.   cur = root;
     
156.   
     
157.   if (cur!=NULL)
     
158.     treeStack.push(cur);
     
159.   
     
160.   while(!treeStack.empty())
     
161.   {
     
162.     cur = treeStack.top();
     
163.     treeStack.pop();
     
164.     if (cur == NULL)
     
165.       continue;
     
166.     if ((cur->lchild==NULL)||                                   //没有左孩子或者
     
167.         ((!treeStack.empty())&&(treeStack.top()==cur->rchild))) //右孩子已经入过栈
     
168.       cout << cur->key << " ";
     
169.     else
     
170.     {
     
171.       treeStack.push(cur->rchild);
     
172.       treeStack.push(cur);
     
173.       if (cur->lchild!=NULL)
     
174.         treeStack.push(cur->lchild);
     
175.     }
     
176.    
     
177.   }
     
178. }
     
179. 
     
180. //先序非递归遍历
     
181. void Tree::preTraverse()
     
182. {
     
183.   stack<node*> treeStack;
     
184.   node *pre, *cur;
     
185.   cur = root;
     
186.   
     
187.   if (cur!=NULL)
     
188.     treeStack.push(cur);
     
189.   
     
190.   while(!treeStack.empty())
     
191.   {
     
192.     cur = treeStack.top();
     
193.     treeStack.pop();
     
194.     cout << cur->key << " ";
     
195.     if (cur->rchild!=NULL)
     
196.       treeStack.push(cur->rchild);
     
197.     if (cur->lchild!=NULL)
     
198.       treeStack.push(cur->lchild);
     
199.   }
     
200. }
     
201. 
     
202. 
     
203. void Tree::traverse()
     
204. {
     
205.   recur_preTraverse(root);
     
206.   cout << endl;
     
207.   preTraverse();
     
208.   cout << endl << endl;
     
209. 
     
210.   recur_inTraverse(root);
     
211.   cout << endl;
     
212.   inTraverse();
     
213.   cout << endl << endl;
     
214.   
     
215.   recur_postTraverse(root);
     
216.   cout << endl;
     
217.   postTraverse();
     
218.   cout << endl << endl;
     
219. }
     
220. 
     
221. int main(int argc, char* argv[])
     
222. {
     
223.   int array[] = {2, 4, 5, 6, 8, 10, 11, 13, 15, 17, 20};
     
224.   Tree tr(array, sizeof(array)/sizeof(array[0]));
     
225.   tr.traverse();
     
226. }
     

复制代码

[ 本帖最后由 ypxing 于 2007-11-16 11:22 编辑 ]

converse

没时间好好看看了,做个标记先~~