樹的前序、中序以及后序遍歷的遞歸算法很簡單，大部分人都能信手拈來，但是非遞歸算法卻不是那么簡單，我們來各個擊破：
樹的結構如下：
1 typedef struct Node {
2 int data;
3 struct Node *left, *right;
4 } BTree;
5
1）前序非遞歸遍歷：
前序遍歷的非遞歸算法相比較而言最簡單，只需要訪問棧頂元素，然后再將棧頂元素出棧，然后再將棧頂元素的右、左孩子入棧即可，不過這里注意的是必須得右孩子先入棧。
程序如下：
1 void PreOrderTraversal(BTree *root) {
2 if (root == NULL) return;
3 stack<BTree *> s;
4 BTree *tmp;
5 s.push(root);
6 while (!s.empty()) {
7 tmp = s.top();
8 s.pop();
9 printf("%d\n", tmp->data);
10 if (tmp->right != NULL) {
11 s.push(tmp->right);
12 }
13 if (tmp->left != NULL) {
14 s.push(tmp->left);
15 }
16 }
17 }
18
這種寫法也非常直觀，但是當遇到中序非遞歸遍歷的時候這種寫法就不能解決問題了，原因是前序遍歷是先訪問根節點，訪問完后就將根節點出棧了，后面棧的操作不再遇到根節點，而中序遍歷的時候必須先訪問左子樹才能訪問根節點，這樣在訪問左子樹之前根節點必須先入棧，但是當某個元素出棧的時候你不能知道它的左孩子是否已經被訪問過了，因此我們需要換一種思路：
其實我們可以模擬中序遍歷的過程：
只要當前節點有左孩子，則必須先去訪問左子樹，而當前節點就得入棧；
如果當前節點為空怎么辦？當然就訪問它的父節點了，也就是棧頂元素；
訪問完棧頂元素之后就需要將當前節點置為棧頂元素的右孩子，然后棧頂元素出棧；
再繼續上述過程直到棧空；
代碼如下：
1 void InOrderTraversal(BTree *root) {
2 if (root == NULL) return;
3 stack<BTree *> s;
4 s.push(root);
5 BTree *cur = root->left; //指向當前要檢查的節點
6 while (cur != NULL || !s.empty()) {
7 while (cur != NULL) { //一直向左走
8 s.push(cur);
9 cur = cur->left;
10 }
11 cur = s.top();
12 s.pop();
13 printf("%d\n", cur->data);
14 cur = cur->right;
15 }
16 }
17
后序遍歷與中序遍歷很相似，但是比中序遍歷復雜的地方是如何判斷該節點的左右子樹都已經訪問過了，按照中序遍歷的寫法左子樹還是先被訪問，沒有問題，但是訪問完左子樹后不能直接訪問當前節點，要判斷當前節點的右子樹是否已經被訪問，如果沒有訪問則應該繼續去訪問右子樹，最后再訪問當前節點：
算法如下：
用cur記錄當前要檢查的節點；
用previsited記錄前一個被訪問（visited）的節點；
這樣只要cur有左孩子，則cur入棧，直到cur沒有左孩子；
然后判斷棧頂元素的右孩子是否是上一個被訪問的節點或者沒有右孩子；（因為后序遍歷的特性，在訪問序列中，當前節點的前驅必然是其右孩子（如果有的話））
如果有右孩子而又沒有被訪問過則cur置為當前節點的右孩子，繼續上述過程；
否則訪問當前節點，并置previsited為當前節點；
重復以上過程直到棧空；
代碼如下：
1 void PostOrderTraversal(BTree *root) {
2 if (root == NULL) return;
3 stack<BTree *> s;
4 BTree *cur = root; //指向當前要檢查的節點
5 BTree *previsited = NULL; //指向前一個被訪問的節點
6 while (cur != NULL || !s.empty()) {
7 while (cur != NULL) { //一直向左走直到為空
8 s.push(cur);
9 cur = cur->left;
10 }
11 cur = s.top();
12 //當前節點的右孩子如果為空或者已經被訪問，則訪問當前節點
13 if (cur->right == NULL || cur->right == previsited) {
14 printf("%d\n", cur->data);
15 s.pop();
16 previsited = cur;
17 cur = NULL;
18 }
19 else { //否則訪問右孩子
20 cur = cur->right;
21 }
22 }
23 }
24
理解樹的非遞歸遍歷非常重要，因為它能幫助更好的理解樹的操作。
posted on 2012-04-26 18:18
myjfm 閱讀(751)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎