上一篇文章，我們對三種遍歷法都有一定的認識了，今天我們要練習用迴圈來實作，難度會深一點！

我們都知道在遍歷一棵樹時，會遇到無數的岔路，那你有想過要怎麼紀錄岔路嗎？
答案是之前介紹過的「堆疊 Stack」，他扮演的是一個暫存的角色。

定義類別

class BST {
private:
    BSTNode *root;
private:
    BST();
    void insert(int); // Non Recursive
    void insert(BSTNode *, int); // Recursive
    void preorder();
    void inorder();
    void postorder();
};

前序遍歷 preorder

概念就是一遇到節點，就輸出其資料！
當遇到岔路時，就將它推進堆疊中。

void BST::preorder() {
    if (this -> root == NULL) return ;
    BSTNode *cur;
    std::stack <BSTNode *> st;
    st.push(this -> root);
    while (st.size()) {
        cur = st.top();
        st.pop();
        std::cout << cur -> data << " -> ";
        if (cur -> right) st.push(cur -> right);
        if (cur -> left) st.push(cur -> left);
    }
}

為什麼是先處理 cur -> right ，而不是 cur -> left 呢？
因為堆疊的順序是越接近上層，越早被存取。而在遍歷的順序中，都是先處理左子節點才處理右子節點，因此我們這樣處理。

中序遍歷 inorder

void BST::inorder() {
    BSTNode *cur = this -> root;
    std::stack <BSTNode *> st;
    while (1) {
        if (cur) {
            st.push(cur);
            cur = cur -> left;
        }
        else {
            if (st.size() == 0) break;
            cur = st.top();
            st.pop();
            cout << cur -> data << " -> ";
            cur = cur -> right;
        }
    }
}

後序遍歷 postorder

大致的規則是
如果左邊可以走就往左邊走，否則就往右邊
如果左右子節點都遍歷過，就輸出節點資料。

void BST::postorder() {
    if (this -> root == NULL) return ;
    BSTNode *cur = this -> root, *temp;
    std::stack <BSTNode *> st;
    while (st.size() || cur) {
        if (cur) {
            st.push(cur);
            cur = cur -> left;
        }
        else {
            temp = st.top() -> right;
            if (temp) {
                cur = temp;
            }
            else {
                temp = st.top();
                st.pop();
                std::cout << temp -> data << " -> ";
                while (st.size() && temp == st.top() -> right) {
                    temp = st.top();
                    st.pop();
                    std::cout << temp -> data << " -> ";
                }
            }
        }
    }
} 

雖然比用遞迴實作更加困難，但是這也不失為一種練習！

下一篇，我們要介紹 BST::levelOrderTraversal()