資料結構——樹（下）

1、二叉樹的遞歸周遊

1、先序周遊

圖示為

代碼實作為

void PreOrderTraversal(BinTree BT){
    if (BT){
        cout << BT->Data;
        PreOrderTraversal(BT->left);
        PreOrderTraversal(BT->right);
    }           

2、中序周遊

void InOrderTraversal(BinTree BT){
    if (BT){
        InOrderTraversal(BT);
        cout << BT->Data;
        InOrderTraversal(BT);
    }
}           

3、後序周遊

void PostOrderTraversal(BinTree BT){
    if (BT){
        PostOrderTraversal(BT);
        PostOrderTraversal(BT);
        cout << BT->Data;
    }
}           

重點說明：先序、前序和後序隻是周遊過程中的通路各結點的順序不同，但是經過的路線是一樣的

2、二叉樹的非遞歸周遊

​ 非遞歸算法的實作基本思路：使用堆棧

1、中序周遊非遞歸周遊方法

具體方法：

• 遇到一個結點，就壓棧，再去周遊它的左子樹
• 當左子樹周遊完成時，從棧頂彈出這個結點并通路它
• 然後按其右指針再去中序周遊該結點的右子樹

void InOrderTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = CreatStack(MAXSIZE);
    while (T || IsEmpty(S)) {
        while(T) {
            Push(S, T);
            T = T->left;
        }
        if (!IsEmpty(S)) {
            T = Pop(S);
            cout << T->Data;
            T = T->right;
        }
    }
}           

2、先序周遊非遞歸周遊方法

• 當遇到一個結點，第一次遇到時直接輸出，再去周遊它的左子樹
• 當左子樹周遊完成，彈出左子樹，再周遊右子樹
• 當右子樹周遊完成，傳回結點

void PreOrderTraversalTest(BinTree BT) {
    BinTree T = BT;
    Stack S = CreatStack(MAXSIZE);
    while (T || IsEmpty(S)) {
        while(T) {
            Push(S, T);
                        cout << T->Data;
            T = T->left;
        }
        if (!IsEmpty(S)){
            T = Pop(S);
            T = T->right;
        }
    }
}           

3、後序周遊非遞歸周遊方法

• 從結點開始，一直壓棧，直到最左子樹
• 彈出最左子樹，傳回結點，周遊右子樹
• 右子樹周遊完畢，傳回結點

代碼實作為：

void PostOrdeTraversal(BinTree BT) {
    BinTree T = BT;
    BinTree pre = nullptr;        //儲存目前結點的前一個結點 
    BinTree Ttop;        //儲存棧頂元素
    Stack S = CreatStack(MAXSIZE);
    while(T || IsEmpty(s)) {
        while(T) {
            Push(T, S);
            T = T->left;
        }
        Ttop = Top(S);        //檢視目前棧頂元素 
        if(Ttop->right == nullptr || Ttop->left == pre){
            //目前結點沒有右子樹或已被通路 
            cout << Ttop->Data;
            pre = Ttop;        //更新前一個結點的位置 
            Pop(S);
        }else{
            T = Ttop->right;        //開始通路右子樹 
        }
    } 
}