二叉樹前序、中序、後序周遊的非遞歸寫法

前序和中序周遊的非遞歸寫法都比較好實作，後序周遊稍微複雜一些.

資料結構定義：

struct Node{

char c;

pNode lchild, rchild;

Node(char c, pNode lchild = nullptr, pNode rchild = nullptr) :

c(c), lchild(lchild), rchild(rchild) {}           

};

申請阿裡雲服務時，可以使用

2000元阿裡雲代金券

，阿裡雲官網領取網址：

https://dashi.aliyun.com/site/yun/youhui

二叉樹形态：

A

/ \

B C

/ / \

D E F G

/ \

H I

前序周遊：

先根周遊，拿到一個節點的指針，先判斷是否為空，不為空就先通路該結點，然後直接進棧，接着周遊左子樹；為空則要從棧中彈出一個節點來，這個時候彈出的結點就是其父親，然後通路其父親的右子樹，直到目前節點為空且棧為空時，算法結束.

阿裡雲伺服器1核2G低至82元/年

，阿裡雲官活動網址：

https://dashi.aliyun.com/site/yun/aliyun

可以用20代金券，即102-20=82。

void preVisitStack(pNode root)

{

stack st;

pNode p = root;

while (p || !st.empty()) {

if (p) {
    visit(p);
    st.push(p);
    p = p->lchild;
} else {
    p = st.top();
    st.pop();
    p = p->rchild;
}           

}

cout << endl;

中序周遊：

和前序周遊一樣，隻不過在通路節點的時候順序不一樣，通路節點的時機是從棧中彈出元素時通路，如果從棧中彈出元素，就意味着目前節點父親的左子樹已經周遊完成，這時候通路父親，就是中序周遊.

void midVisitStack(pNode root)

if (p) {
    st.push(p);
    p = p->lchild;
} else {
    p = st.top();
    visit(p);
    st.pop();
    p = p->rchild;
}           

後序周遊：

後續周遊就不一樣了，首先肯定是先通路左子樹，把父親節點儲存于棧中，問題是當元素從棧中彈出的時候，我們無法判斷這個時候是該通路其右子樹還是通路父親節點，于是我們就需要一個标記，當通路左子樹時我們把父親節點的标記設為1，表示下一步如果彈出該節點，就通路其右子樹；彈出一個節點時，我們要判斷該節點的标記，如果是1，則通路其右子樹，并把該節點的标記設定成2，表示下一步就通路該節點，然後把該節點繼續入棧，如果是2，那麼表示通路該節點，通路并且丢棄該節點.

為了不繼續添加新的資料結構，我是用了STL中的pair來封裝節點與标記.

void backVisitStack(pNode root)

stack > st;

if (p) {
    st.push(make_pair(p, 1));
    p = p->lchild;
} else {
    auto now = st.top();
    st.pop();
    if (now.second == 1) {
        st.push(make_pair(now.first, 2));
        p = now.first->rchild;
    } else
        visit(now.first);
}           

完整測試代碼：

include

using namespace std;

typedef struct Node *pNode;

c(c), lchild(lchild), rchild(rchild) {}           

pNode build()

/*

A
   /  \
 B     C
/ \   / \           

D E F G

/ \
   H   I           

*/

pNode root = new Node('A');

root->lchild = new Node('B');

root->rchild = new Node('C');

root->lchild->lchild = new Node('D');

root->lchild->rchild = new Node('E');

root->rchild->lchild = new Node('F');

root->rchild->rchild = new Node('G');

root->rchild->lchild->lchild = new Node('H');

root->rchild->lchild->rchild = new Node('I');

return root;

void visit(pNode x)

cout << x->c << " ";

if (p) {
    visit(p);
    st.push(p);
    p = p->lchild;
} else {
    p = st.top();
    st.pop();
    p = p->rchild;
}           

if (p) {
    st.push(p);
    p = p->lchild;
} else {
    p = st.top();
    visit(p);
    st.pop();
    p = p->rchild;
}           

if (p) {
    st.push(make_pair(p, 1));
    p = p->lchild;
} else {
    auto now = st.top();
    st.pop();
    if (now.second == 1) {
        st.push(make_pair(now.first, 2));
        p = now.first->rchild;
    } else
        visit(now.first);
}           

int main()

pNode root = build();

preVisitStack(root);

midVisitStack(root);

backVisitStack(root);

測試結果：

依次為前序、中序、後序周遊的結果.

A B D E C F H I G

D B E A H F I C G

D E B H I F G C A