樹的前序、中序以及后序遍歷的遞歸算法很簡單，大部分人都能信手拈來，但是非遞歸算法卻不是那么簡單，我們來各個(gè)擊破：
樹的結(jié)構(gòu)如下：
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
這種寫法也非常直觀，但是當(dāng)遇到中序非遞歸遍歷的時(shí)候這種寫法就不能解決問題了，原因是前序遍歷是先訪問根節(jié)點(diǎn)，訪問完后就將根節(jié)點(diǎn)出棧了，后面棧的操作不再遇到根節(jié)點(diǎn)，而中序遍歷的時(shí)候必須先訪問左子樹才能訪問根節(jié)點(diǎn)，這樣在訪問左子樹之前根節(jié)點(diǎn)必須先入棧，但是當(dāng)某個(gè)元素出棧的時(shí)候你不能知道它的左孩子是否已經(jīng)被訪問過了，因此我們需要換一種思路：
其實(shí)我們可以模擬中序遍歷的過程：
只要當(dāng)前節(jié)點(diǎn)有左孩子，則必須先去訪問左子樹，而當(dāng)前節(jié)點(diǎn)就得入棧；
如果當(dāng)前節(jié)點(diǎn)為空怎么辦？當(dāng)然就訪問它的父節(jié)點(diǎn)了，也就是棧頂元素；
訪問完棧頂元素之后就需要將當(dāng)前節(jié)點(diǎn)置為棧頂元素的右孩子，然后棧頂元素出棧；
再繼續(xù)上述過程直到棧空；
代碼如下：
1 void InOrderTraversal(BTree *root) {
2 if (root == NULL) return;
3 stack<BTree *> s;
4 s.push(root);
5 BTree *cur = root->left; //指向當(dāng)前要檢查的節(jié)點(diǎn)
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
后序遍歷與中序遍歷很相似，但是比中序遍歷復(fù)雜的地方是如何判斷該節(jié)點(diǎn)的左右子樹都已經(jīng)訪問過了，按照中序遍歷的寫法左子樹還是先被訪問，沒有問題，但是訪問完左子樹后不能直接訪問當(dāng)前節(jié)點(diǎn)，要判斷當(dāng)前節(jié)點(diǎn)的右子樹是否已經(jīng)被訪問，如果沒有訪問則應(yīng)該繼續(xù)去訪問右子樹，最后再訪問當(dāng)前節(jié)點(diǎn)：
算法如下：
用cur記錄當(dāng)前要檢查的節(jié)點(diǎn)；
用previsited記錄前一個(gè)被訪問（visited）的節(jié)點(diǎn)；
這樣只要cur有左孩子，則cur入棧，直到cur沒有左孩子；
然后判斷棧頂元素的右孩子是否是上一個(gè)被訪問的節(jié)點(diǎn)或者沒有右孩子；（因?yàn)楹笮虮闅v的特性，在訪問序列中，當(dāng)前節(jié)點(diǎn)的前驅(qū)必然是其右孩子（如果有的話））
如果有右孩子而又沒有被訪問過則cur置為當(dāng)前節(jié)點(diǎn)的右孩子，繼續(xù)上述過程；
否則訪問當(dāng)前節(jié)點(diǎn)，并置previsited為當(dāng)前節(jié)點(diǎn)；
重復(fù)以上過程直到棧空；
代碼如下：
1 void PostOrderTraversal(BTree *root) {
2 if (root == NULL) return;
3 stack<BTree *> s;
4 BTree *cur = root; //指向當(dāng)前要檢查的節(jié)點(diǎn)
5 BTree *previsited = NULL; //指向前一個(gè)被訪問的節(jié)點(diǎn)
6 while (cur != NULL || !s.empty()) {
7 while (cur != NULL) { //一直向左走直到為空
8 s.push(cur);
9 cur = cur->left;
10 }
11 cur = s.top();
12 //當(dāng)前節(jié)點(diǎn)的右孩子如果為空或者已經(jīng)被訪問，則訪問當(dāng)前節(jié)點(diǎn)
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
理解樹的非遞歸遍歷非常重要，因?yàn)樗軒椭玫睦斫鈽涞牟僮鳌?
posted on 2012-04-26 18:18
myjfm 閱讀(739)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)