二叉树的遍历

二叉树的结构：

1 typedef int ElementType;
2 typedef struct TNode *Position;
3 typedef Position BinTree;
4 struct TNode
5 {
6     ElementType Data;
7     BinTree Left;
8     BinTree Right;
9 };

二叉树先中后序遍历（递归实现）:

 1 //递归实现中序遍历
 2 void InorderTraversal(BinTree BT)
 3 {
 4     if(BT)   //如果不是空树
 5     {
 6         InorderTraversal(BT->Left);
 7         printf("%d", BT->Data);       //此处假设对BT节点的访问就是打印数据
 8         InorderTraversal(BT->Right);
 9     }
10 
11 }
12 
13 
14 //递归实现先序遍历
15 void PreorderTraversal(BinTree BT)
16 {
17     if(BT)   //如果不是空树
18     {
19         printf("%d", BT->Data);
20         PreorderTraversal(BT->Left);
21         PreorderTraversal(BT->Right);
22     }
23 }
24 
25 
26 //递归实现后序遍历
27 void PostorderTraversal(BinTree BT)
28 {
29     if(BT)   //如果不是空树
30     {
31         PostorderTraversal(BT->Left);
32         PostorderTraversal(BT->Right);
33         printf("%d", BT->Data);
34     }
35 }

使用C++:

非递归实现中序遍历：

 1 //非递归实现中序遍历
 2 void InorderTraversal(BinTree BT)
 3 {
 4     stack<TNode *> S;
 5     BinTree T = BT;
 6     while(T || !S.empty())
 7     {
 8         while(T)
 9         {
10             S.push(T);
11             T = T->Left;
12         }
13         if(!S.empty())
14         {
15             T = S.top();
16             printf("%d", T->Data);
17             S.pop();
18             T = T->Right;
19         }
20     }
21 }

非递归实现先序遍历：

 1 //非递归实现先序遍历
 2 void preOrder(node* p)
 3 {
 4     stack<node*> s;
 5     s.push(p);
 6     while(!s.empty())
 7     {
 8         node* t =s.top();
 9         s.pop();
10         // 访问结点
11         cout << t->data;
12         // 先把右孩子入栈，因为栈是后进先出 
13         if(t->right)
14             s.push(t->right);
15         // 再把左孩子入栈
16         if(t->left)
17             s.push(t->left);
18     }
19     
20 }

非递归实现后序遍历：

因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用堆栈来存储节点，必须分清返回根节点时，是从左子树返回的，还从右子树返回的。

所以，使用辅助指针r，其指向最近访问过的节点。也可以在节点中增加一个标志域，记录是否已被访问。

 1 //非递归实现后序遍历
 2 void PostOrder3(BinTree BT)     
 3 {
 4     BinTree T = BT, r = NULL;   //r用来标记最近访问过的节点
 5     stack<TNode *> s;
 6     while (T || !s.empty())
 7     {
 8         if (T)  //T非空时，遇到一个节点就把这个节点入栈，走到最左边
 9         {
10             s.push(T);
11             T = T->Left;
12         }
13         else
14         {
15             T = s.top();
16             if (T->Right && T->Right != r)//右子树存在且未被访问
17                 T = T->Right;
18             else
19             {
20                 s.pop();
21                 printf("%d", T->Data);
22                 r = T;       //记录最近访问过的节点
23                 T = NULL;    //节点访问完后，重置T指针
24             }
25         }//else
26     }//while
27 
28 }

二叉树的层序遍历：

(1) 从队列中取出一个元素；

(2) 访问该元素所指节点；

(3) 若该元素所指节点的左右孩子节点非空，则将其左右孩子节点顺序入队。

不断执行这三步操作，直到队列为空，再无元素可取，二叉树的层序遍历就完成了。

 1 //二叉树的层序遍历
 2 void LeverorderTraversal(BinTree BT)
 3 {
 4     queue<TNode *> Q;
 5     BinTree T;
 6     if(!BT)     //如果是空树则直接返回
 7         return;
 8 　　 Q.push(BT);
 9     while(!Q.empty())
10     {
11         T = Q.front();
12         printf("%d", T->Data);
13         Q.pop();
14         if(T->Left)
15             Q.push(T->Left);
16         if(T->Right)
17             Q.push(T->Right);
18     }
19 }