二叉树的基础问题

http://blog.csdn.net/zzran/article/details/8220423

2012

先给定一个二叉树的图作为样例：

图中下边没有给出的表示为空，图画的不好，将就着看吧。

下面的代码中分别给出了二叉树的前中后的递归遍历和非递归遍历，最后还给出层次遍历。

[cpp] view plain copy

1. #include<iostream>  
2. #include<deque>  
3. #include<stack>  
4. using namespace std;  
5. #define NIL '#'  
6. typedef struct tree_node{  
7.     char data;  
8.     struct tree_node *lchild,*rchild;  
9. }BiTNode,*BiTree;  
10. void create_tree(BiTree *T) {  
11.     char ch;   
12.     scanf("%c", &ch);  
13.     if(ch == NIL){  
14.         *T = NULL;  
15.     } else {  
16.         *T = (BiTNode*)malloc(sizeof(BiTNode));  
17.         (*T)->data = ch;  
18.         create_tree(&(*T)->lchild);  
19.         create_tree(&(*T)->rchild);  
20.     }  
21. }  
22. void pre_order_traverse_recursive(BiTree T) { //前根递归遍历  
23.     if(T) {  
24.         cout << T->data << " ";  
25.         pre_order_traverse_recursive(T->lchild);  
26.         pre_order_traverse_recursive(T->rchild);  
27.     }  
28. }  
29.   
30. void pre_order_traverse_iterative(BiTree T) {  //前根非递归遍历  
31.     stack<BiTNode *> m_stack;  
32.     m_stack.push(T);  
33.     BiTNode *p;  
34.     while(!m_stack.empty()) {  
35.         while((p = m_stack.top()) != NULL) {  
36.             cout << p->data << " ";  
37.             m_stack.push(p->lchild);  
38.         }  
39.           
40.         m_stack.pop();  
41.   
42.         if(!m_stack.empty()) {  
43.             p = m_stack.top();  
44.             m_stack.pop();  
45.             m_stack.push(p->rchild);  
46.         }  
47.     }  
48. }  
49. void in_order_traverse_recursive(BiTree T) { //中根递归遍历  
50.     if(T) {  
51.         in_order_traverse_recursive(T->lchild);  
52.         cout << T->data << " ";  
53.         in_order_traverse_recursive(T->rchild);  
54.     }  
55. }  
56. void in_order_traverse_iterative(BiTree T) { //中根非递归遍历  
57.     stack<BiTNode*> m_stack;  
58.     m_stack.push(T);  
59.     BiTNode *p;  
60.   
61.     while(!m_stack.empty()) {  
62.         while((p = m_stack.top()) != NULL)   
63.             m_stack.push(p->lchild);  
64.   
65.         m_stack.pop();  
66.   
67.         if(!m_stack.empty()) {  
68.             p = m_stack.top();  
69.             m_stack.pop();  
70.             cout << p->data << " ";  
71.             m_stack.push(p->rchild);  
72.         }  
73.     }  
74. }  
75.   
76. void post_order_traverse_recursive(BiTree T) { //后根递归遍历  
77.     if(T) {  
78.         post_order_traverse_recursive(T->lchild);  
79.         post_order_traverse_recursive(T->rchild);  
80.         cout << T->data << " ";  
81.     }  
82. }  
83.   
84. void post_order_traverse_iterative(BiTree T) { //后根非递归遍历  
85.     stack<BiTNode*> m_stack;  
86.     BiTNode *p;  
87.     BiTNode *r;  
88.     p = T;  
89.     while(p || !m_stack.empty()) {  
90.         if(p) {  
91.             m_stack.push(p);  
92.             p = p->lchild;  
93.         } else {  
94.             p = m_stack.top();  
95.             if(p->rchild && p->rchild != r) {  
96.                 p = p->rchild;  
97.                 m_stack.push(p);  
98.                 p = p->lchild;  
99.             } else {  
100.                 p = m_stack.top();  
101.                 m_stack.pop();  
102.                 cout << p->data << " ";  
103.                 r = p;  
104.                 p = NULL;  
105.             }  
106.         }  
107.     }  
108. }  
109.   
110. void horizontal_traverse(BiTree T) {  
111.     deque<BiTNode *> m_deque;  
112.     m_deque.push_back(T);  
113.     while(!m_deque.empty()) {  
114.         BiTNode *temp = m_deque.front();  
115.         m_deque.pop_front();  
116.         cout << temp->data << " ";  
117.         if(temp->lchild)  
118.             m_deque.push_back(temp->lchild);  
119.         if(temp->rchild)  
120.             m_deque.push_back(temp->rchild);  
121.     }  
122. }  
123. void main() {  
124.     BiTree T = NULL;  
125.     create_tree(&T);  
126.   
127.     //先根遍历  
128.     cout << "pre_order_traverse_recursive:";  
129.     pre_order_traverse_recursive(T);  
130.     cout << endl;  
131.   
132.     cout << "pre_order_traverse_iterative:";  
133.     pre_order_traverse_iterative(T);  
134.     cout << endl;  
135.   
136.     //中根遍历  
137.     cout << "in_order_traverse_recursive:";  
138.     in_order_traverse_recursive(T);  
139.     cout << endl;  
140.   
141.     cout << "in_order_traverse_iterative:";  
142.     in_order_traverse_iterative(T);  
143.     cout << endl;  
144.   
145.     //后根遍历  
146.     cout << "post_order_traverse_iterative:";  
147.     post_order_traverse_recursive(T);  
148.     cout << endl;  
149.   
150.     cout << "post_order_traverse_iterative:";  
151.     post_order_traverse_iterative(T);  
152.     cout << endl;  
153.     // 水平遍历  
154.     cout <<  "horizontal traverse:";  
155.     horizontal_traverse(T);  
156.     cout << endl;  
157.       
158. }