如下圖，對圖中二叉樹遍歷：

先序為:ABDNCEFGHIJKLMOQP
中序為:DNBCGFEAHJKILOQMP
后序為:NDGFECBKJQOPMLIHA

二叉樹示意.jpg

假設樹節(jié)點如下：

struct Node{
    char data;
    Node *left;
    Node *right;
};

遞歸實現(xiàn)

先序

void preOrder(Node *root){
    cout<<root->data;
    preOrder(root->left);
    preOder(root->right);
}

中序

void inOrder(Node *root){
    preOrder(root->left);
    cout<<root->data;
    preOder(root->right);
}

后序

void postOrder(Node *root){
    preOrder(root->left);
    preOder(root->right);
    cout<<root->data;
}

非遞歸實現(xiàn)

先序

對于任一結點P：
1)訪問結點P，并將結點P入棧;
2)判斷結點P的左孩子是否為空芜果，若為空盗尸，則取棧頂結點并進行出棧操作量愧，并將棧頂結點的右孩子置為當前的結點P凯傲，循環(huán)至1);若不為空搪泳，則將P的左孩子置為當前的結點P;
3)直到P為NULL并且棧為空凹耙，則遍歷結束姿现。

void preOrderS(Node *root)   
{
    stack<Node*> s;
    Node *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->left;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->right;
        }
    }
}

中序

對于任一結點P，
1)若其左孩子不為空肖抱，則將P入棧并將P的左孩子置為當前的P备典，然后對當前結點P再進行相同的處理；
2)若其左孩子為空意述，則取棧頂元素并進行出棧操作提佣，訪問該棧頂結點，然后將當前的P置為棧頂結點的右孩子荤崇；
3)直到P為NULL并且棧為空則遍歷結束拌屏。

void inOrderS(Node *root){
    stack<Node*> s;
    Node *p=root;
    while(p!=NULL||!s.empty()){
        while(p!=NULL)){
            s.push(p);
            p=p->left;
        }
        if(!s.empty()){
            p=s.top();
            s.pop();
            cout<<p->data;
            p=p->right;
        }
    }
}

后序

因為后序非遞歸遍歷二叉樹的順序是先訪問左子樹，再訪問右子樹术荤，最后訪問根節(jié)點倚喂。當用堆棧來存儲節(jié)點，必須分清返回根節(jié)點時瓣戚，是從左子樹返回的端圈，還從右子樹返回的。所以子库，使用輔助指針r舱权，其指向最近訪問過的節(jié)點。也可以在節(jié)點中增加一個標志域仑嗅，記錄是否已被訪問宴倍。

void PostOrderS(Node *root) {
    Node *p = root, *r = NULL;
    stack<Node*> s;
    while (p!=NULL || !s.empty()) {
        if (p!=NULL) {//走到最左邊
            s.push(p);
            p = p->left;
        }
        else {
            p = s.top();
            if (p->right!=NULL && p->right != r)//右子樹存在，未被訪問
                p = p->right;
            else {
                s.pop();
                visit(p->val);
                r = p;//記錄最近訪問過的節(jié)點
                p = NULL;//節(jié)點訪問完后仓技，重置p指針
            }
        }//else
    }//while
}