二叉树操作总结

　　对于二叉树，有前序、中序、后序三种遍历方法，由于树的定义本身就是递归定义的，故采用递归方法实现三种遍历简洁易懂。若采用非递归访问，则需要使用栈来模拟递归的实现。三种遍历的非递归算法中，前序和后序较容易，而后序相对较难。

	前序遍历	递归	非递归
树的遍历	中序遍历	递归	非递归
树的遍历	后序遍历	递归	非递归
	层次遍历
计算树高
计算结点数

1. 前序遍历【访问顺序：根结点-左孩子-右孩子】

　　a> 前序遍历递归实现

1 void PreOrderRecursively(BinaryTreeNode *root)
2 {//递归前序遍历[根，左，右]
3     if(root != NULL)
4     {
5         cout << root->data <<" ";
6         PreOrderRecursively(root->pLeft);
7         PreOrderRecursively(root->pRight);
8     }
9 }

　　b> 前序遍历非递归实现

 1 void PreOrder(BinaryTreeNode *root)
 2 {//非递归前序遍历：借助于栈，先将根入栈，只要栈不为空，就弹出一个结点，同时将其右孩子、左孩子入栈。
 3  //                   注意：右子树先入栈，以保证右子树在栈中处于左子树的下面[栈：后进先出]
 4     if(root == NULL)
 5         return;
 6     stack<BinaryTreeNode*> s;
 7     s.push(root);//根入栈
 8 
 9     BinaryTreeNode *temp;
10     while(!s.empty())//栈不为空
11     {
12         temp = s.top();//访问栈顶结点
13         cout << temp->data<<" ";
14         s.pop();//出栈
15         if(temp->pRight)
16             s.push(temp->pRight);
17         if(temp->pLeft)
18             s.push(temp->pLeft);
19     }
20 }

2. 中序遍历【访问顺序：左孩子-根结点-右孩子】

　　a> 中序遍历递归实现

1 void InOrderRecursively(BinaryTreeNode *root)
2 {//递归中序遍历[左，根，右]
3     if(root != NULL)
4     {
5         InOrderRecursively(root->pLeft);
6         cout << root->data << " ";
7         InOrderRecursively(root->pRight);
8     }
9 }

　　b> 中序遍历非递归实现

 1 void InOrder(BinaryTreeNode *root)
 2 {/*
 3     非递归中序遍历：
 4         对任一结点P,
 5         1）若其左孩子不为空，则将P入栈，将其左孩子置为当前P,然后对当前结点P进行相同处理；
 6         2) 若其左孩子为空，则取栈顶元素并出栈，访问该栈顶结点，然后将当前的P职位栈顶结点的右孩子
 7         3) 直到P为NULL且栈为空，则遍历结束
 8  */
 9     if(root == NULL)
10         return;
11 
12     stack<BinaryTreeNode*> s;
13     BinaryTreeNode *cur = root;
14 
15     while(cur != NULL || !s.empty())//P为NULL且栈为空时终止
16     {
17         while(cur != NULL)//直到达到最左边
18         {
19             s.push(cur);
20             cur = cur->pLeft;
21         }
22 
23         if(!s.empty())//第二种情况
24         {
25             cur = s.top();
26             cout<<cur->data<<" ";
27             s.pop();
28             cur = cur->pRight;
29         }
30     }
31 }

3. 后序遍历【访问顺序：左孩子-右孩子-根结点】

　　a> 后序遍历递归实现

1 void PostOrderRecursively(BinaryTreeNode *root)
2 {//递归后序遍历[左，右，根]
3     if(root != NULL)
4     {
5         PostOrderRecursively(root->pLeft);
6         PostOrderRecursively(root->pRight);
7         cout << root->data << " ";
8     }
9 }

　　b>后序遍历非递归实现

 1 void PostOrder(BinaryTreeNode *root)
 2 {/*
 3     非递归后序遍历：[难点：保证根结点在左孩子和右孩子被访问之后才能被访问]
 4         根结点入栈
 5         对任一栈顶元素P:
 6         1)若P不存在左孩子和右孩子，直接访问它；或P存在左孩子或右孩子，但其左孩子或右孩子已被访问过，
 7           同样直接访问它。然后将P出栈，pre置为P
 8         2)若并非1)中的两种情况，则将P的右孩子和左孩子依次入栈，以保证每次取栈顶元素时，左孩子在右孩子
 9           之前被访问，左孩子和右孩子都在根结点之前被访问        
10  */
11     if(root == NULL)
12         return;
13     
14     stack<BinaryTreeNode*> s;
15     BinaryTreeNode *cur;
16     BinaryTreeNode *pre = NULL;//指示上次被访问的结点
17     s.push(root);
18 
19     while(!s.empty())//栈不为空时循环
20     {
21         cur = s.top();//取栈顶元素
22 
23         //当前结点无孩子结点或孩子节点都已被访问
24         if((cur->pLeft == NULL && cur->pRight == NULL) || 
25             (pre!=NULL && (pre==cur->pLeft || pre==cur->pRight)))
26         {
27             cout << cur->data<<" ";//访问该栈顶元素
28             s.pop();//出栈
29             pre = cur;//更新pre
30         }
31         else
32         {
33             if(cur->pRight != NULL)//右孩子入栈
34                 s.push(cur->pRight);
35             if(cur->pLeft != NULL)//左孩子入栈
36                 s.push(cur->pLeft);
37         }
38     }
39 }

4.层次遍历

 1 void LevelOrder(BinaryTreeNode *root)
 2 {//层次遍历：只有非递归的方法
 3  //借助队列来实现：根结点入队，只要队列不为空，访问队首元素并出队，将其左孩子和右孩子依次入队
 4     if(root == NULL)
 5         return;
 6     queue<BinaryTreeNode *> q;
 7     q.push(root);
 8     BinaryTreeNode *cur;
 9     while(!q.empty())
10     {
11         cur = q.front();//队首元素
12         cout << cur->data << " ";
13         q.pop();//出队
14         if(cur->pLeft != NULL)
15             q.push(cur->pLeft);
16         if(cur->pRight != NULL)
17             q.push(cur->pRight);
18     }
19 }

5.计算树高和结点数

 1 int TreeHeight(BinaryTreeNode *root)//计算树高
 2 {//计算树高
 3     if(root == NULL)//空树
 4         return 0;
 5     int heightLeft = TreeHeight(root->pLeft);//左子树高度
 6     int heightRight = TreeHeight(root->pRight);//右子树高度
 7     if(heightLeft > heightRight)
 8         return ++heightLeft;
 9     else
10         return ++heightRight;
11 }
12 
13 int CountNode(BinaryTreeNode *root)
14 {//计算树的结点数
15     if(root == NULL)
16         return 0;
17     return 1+CountNode(root->pLeft)+CountNode(root->pRight);
18 }

【完整代码】

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <stack>
  4 #include <queue>
  5 using namespace std;
  6 
  7 struct BinaryTreeNode
  8 {
  9     int data;
 10     BinaryTreeNode *pLeft;//左子树
 11     BinaryTreeNode *pRight;//右子树
 12 
 13     BinaryTreeNode(int a):data(a),pLeft(NULL),pRight(NULL) {}
 14 };
 15 
 16 void CreateBinaryTree(BinaryTreeNode **root)//二级指针作为函数参数
 17 {//按先序遍历创建二叉树:操作不是很容易懂!!!
 18     char ch;//要插入的数据
 19     //cout << "input root data:";
 20     cin >> ch;
 21     if(ch == '#')//表示为空
 22         *root = NULL;
 23     else
 24     {
 25         *root = new BinaryTreeNode(ch);
 26         cout << "input left child:";//此时不接受输入cin!!!
 27         CreateBinaryTree(&((*root)->pLeft));
 28         cout << "input right child:";
 29         CreateBinaryTree(&((*root)->pRight));
 30     }
 31 }
 32 
 33 
 34 void ConnectTreeNodes(BinaryTreeNode *pRoot,BinaryTreeNode *pLeft,BinaryTreeNode *pRight)
 35 {
 36     if(pRoot != NULL)
 37     {
 38         //if(pLeft)//不是pRoot->pLeft
 39             pRoot->pLeft = pLeft;
 40         //if(pRight)
 41             pRoot->pRight = pRight;
 42     }
 43 }
 44 
 45 void PreOrderRecursively(BinaryTreeNode *root)
 46 {//递归前序遍历[根，左，右]
 47     if(root != NULL)
 48     {
 49         cout << root->data <<" ";
 50         PreOrderRecursively(root->pLeft);
 51         PreOrderRecursively(root->pRight);
 52     }
 53 }
 54 
 55 void PreOrder(BinaryTreeNode *root)
 56 {//非递归前序遍历：借助于栈，先将根入栈，只要栈不为空，就弹出一个结点，同时将其右孩子、左孩子入栈。
 57  //                   注意：右子树先入栈，以保证右子树在栈中处于左子树的下面[栈：后进先出]
 58     if(root == NULL)
 59         return;
 60     stack<BinaryTreeNode*> s;
 61     s.push(root);//根入栈
 62 
 63     BinaryTreeNode *temp;
 64     while(!s.empty())//栈不为空
 65     {
 66         temp = s.top();//访问栈顶结点
 67         cout << temp->data<<" ";
 68         s.pop();//出栈
 69         if(temp->pRight)
 70             s.push(temp->pRight);
 71         if(temp->pLeft)
 72             s.push(temp->pLeft);
 73     }
 74 }
 75 

 76 void InOrderRecursively(BinaryTreeNode *root)
 77 {//递归中序遍历[左，根，右]
 78     if(root != NULL)
 79     {
 80         InOrderRecursively(root->pLeft);
 81         cout << root->data << " ";
 82         InOrderRecursively(root->pRight);
 83     }
 84 }
 85 
 86 void InOrder(BinaryTreeNode *root)
 87 {/*
 88     非递归中序遍历：
 89         对任一结点P,
 90         1）若其左孩子不为空，则将P入栈，将其左孩子置为当前P,然后对当前结点P进行相同处理；
 91         2) 若其左孩子为空，则取栈顶元素并出栈，访问该栈顶结点，然后将当前的P职位栈顶结点的右孩子
 92         3) 直到P为NULL且栈为空，则遍历结束
 93  */
 94     if(root == NULL)
 95         return;
 96 
 97     stack<BinaryTreeNode*> s;
 98     BinaryTreeNode *cur = root;
 99 
100     while(cur != NULL || !s.empty())//P为NULL且栈为空时终止
101     {
102         while(cur != NULL)//直到达到最左边
103         {
104             s.push(cur);
105             cur = cur->pLeft;
106         }
107 
108         if(!s.empty())//第二种情况
109         {
110             cur = s.top();
111             cout<<cur->data<<" ";
112             s.pop();
113             cur = cur->pRight;
114         }
115     }
116 }
117 
118 void PostOrderRecursively(BinaryTreeNode *root)
119 {//递归后序遍历[左，右，根]
120     if(root != NULL)
121     {
122         PostOrderRecursively(root->pLeft);
123         PostOrderRecursively(root->pRight);
124         cout << root->data << " ";
125     }
126 }
127 
128 void PostOrder(BinaryTreeNode *root)
129 {/*
130     非递归后序遍历：[难点：保证根结点在左孩子和右孩子被访问之后才能被访问]
131         根结点入栈
132         对任一栈顶元素P:
133         1)若P不存在左孩子和右孩子，直接访问它；或P存在左孩子或右孩子，但其左孩子或右孩子已被访问过，
134           同样直接访问它。然后将P出栈，pre置为P
135         2)若并非1)中的两种情况，则将P的右孩子和左孩子依次入栈，以保证每次取栈顶元素时，左孩子在右孩子
136           之前被访问，左孩子和右孩子都在根结点之前被访问        
137  */
138     if(root == NULL)
139         return;
140     
141     stack<BinaryTreeNode*> s;
142     BinaryTreeNode *cur;
143     BinaryTreeNode *pre = NULL;//指示上次被访问的结点
144     s.push(root);
145 
146     while(!s.empty())//栈不为空时循环
147     {
148         cur = s.top();//取栈顶元素
149 
150         //当前结点无孩子结点或孩子节点都已被访问
151         if((cur->pLeft == NULL && cur->pRight == NULL) || 
152             (pre!=NULL && (pre==cur->pLeft || pre==cur->pRight)))
153         {
154             cout << cur->data<<" ";//访问该栈顶元素
155             s.pop();//出栈
156             pre = cur;//更新pre
157         }
158         else
159         {
160             if(cur->pRight != NULL)//右孩子入栈
161                 s.push(cur->pRight);
162             if(cur->pLeft != NULL)//左孩子入栈
163                 s.push(cur->pLeft);
164         }
165     }
166 }
167 
168 void LevelOrder(BinaryTreeNode *root)
169 {//层次遍历：只有非递归的方法
170  //借助队列来实现：根结点入队，只要队列不为空，访问队首元素并出队，将其左孩子和右孩子依次入队
171     if(root == NULL)
172         return;
173     queue<BinaryTreeNode *> q;
174     q.push(root);
175     BinaryTreeNode *cur;
176     while(!q.empty())
177     {
178         cur = q.front();//队首元素
179         cout << cur->data << " ";
180         q.pop();//出队
181         if(cur->pLeft != NULL)
182             q.push(cur->pLeft);
183         if(cur->pRight != NULL)
184             q.push(cur->pRight);
185     }
186 }
187 
188 int TreeHeight(BinaryTreeNode *root)//计算树高
189 {//计算树高
190     if(root == NULL)//空树
191         return 0;
192     int heightLeft = TreeHeight(root->pLeft);//左子树高度
193     int heightRight = TreeHeight(root->pRight);//右子树高度
194     if(heightLeft > heightRight)
195         return ++heightLeft;
196     else
197         return ++heightRight;
198 }
199 
200 int CountNode(BinaryTreeNode *root)
201 {//计算树的结点数
202     if(root == NULL)
203         return 0;
204     return 1+CountNode(root->pLeft)+CountNode(root->pRight);
205 }
206 
207 BinaryTreeNode* TestCreate()
208 {//建树的测试函数
209     /*
210         建树
211                 1
212               /   
213             2       3
214            /        
215           4   5       6       
216          /
217         7
218     */
219     BinaryTreeNode* pNodeA1 = new BinaryTreeNode(1);
220     BinaryTreeNode* pNodeA2 = new BinaryTreeNode(2);
221     BinaryTreeNode* pNodeA3 = new BinaryTreeNode(3);
222     BinaryTreeNode* pNodeA4 = new BinaryTreeNode(4);
223     BinaryTreeNode* pNodeA5 = new BinaryTreeNode(5);
224     BinaryTreeNode* pNodeA6 = new BinaryTreeNode(6);
225     BinaryTreeNode* pNodeA7 = new BinaryTreeNode(7);
226 
227     ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
228     ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
229     ConnectTreeNodes(pNodeA3, NULL, pNodeA6);
230     ConnectTreeNodes(pNodeA4, pNodeA7,NULL);
231 
232     cout << endl << "PreOrder:";
233     PreOrder(pNodeA1);//1 2 4 7 5 3 6
234     cout <<  endl << "InOrder:";
235     InOrder(pNodeA1);//7 4 2 5 1 3 6
236     cout << endl <<  "PostOrder:";
237     PostOrder(pNodeA1);//7 4 5 2 6 3 1
238     cout <<  endl << "LevelOrder:";
239     LevelOrder(pNodeA1);//1 2 3 4 5 6 7
240 
241     return pNodeA1;//因为没有delete，故返回后仍可访问
242 }
243 int main()
244 {
245     BinaryTreeNode *root = TestCreate();//定义根结点
246     
247     cout <<  endl << "LevelOrder:";
248     LevelOrder(root);//1 2 3 4 5 6 7
249     
250 }

View Code

参考：http://blog.csdn.net/xiajun07061225/article/details/12760627

　　 http://blog.csdn.net/hackbuteer1/article/details/6583988