二叉樹

前言

二叉樹的遍歷主要有深度優先遍歷和廣度優先遍歷，深度優先遍歷是優先訪問一個子樹上的所有節點，訪問的屬性是豎向的，而廣度優先遍歷則是優先訪問同一層的所有節點，訪問屬性是橫向的。

深度優先遍歷

深度優先遍歷主要有三種順序：

• 前序遍歷 —— 根左右
• 中序遍歷 —— 左根右
• 後序遍歷 —— 左右根

這三種遍歷順序用遞歸可以很容易實現，主要講的是非遞歸的實現方法。而要使用迭代的方法來遍歷二叉樹，需要用到棧的特性。

前序遍歷（非遞歸C++）

演算法：

1. 根節點入棧
2. 訪問棧頂元素並將其出棧
3. 將左右子樹入棧，由於訪問順序是"根左右"，且使用的是棧，因此右子樹先於左子樹入棧
4. 重覆步驟2、3，直到棧為空

void preOrder(BTNode* root) {
    stack<BTNode*> S;
    BTNode* cur = NULL;
    if(root == NULL)
        return;
    S.push(root);   //根節點入棧
    while(!S.empty()) {
        //訪問順序"根左右"
        cur = S.top();
        cout<<""<<cur->data<<"\n";
        //出棧訪問過的節點
        S.pop();
        //先入棧右子樹，這樣就可以先訪問左子樹
        if(cur->right != NULL)
            S.push(cur->right);
        if(cur->left != NULL)
            S.push(cur->left);
    }
}

中序遍歷（非遞歸C++）

演算法：

1. 根節點入棧
2. 遍歷左孩子節點，入棧，直到左子樹為空
3. 訪問棧頂節點並將棧頂節點出棧
4. 對右子樹進行步驟2、3，訪問當前節點的右子樹
5. 重覆步驟2、3、4，直到棧空

void midOrder(BTNode* root) {
    stack<BTNode*> S;
    BTNode* cur = NULL;
    if(root == NULL)
        return;
    S.push(root);   //根節點入棧
    cur = root;
    while(!S.empty()) {
        //訪問順序"左根右"
        while(cur) {    //將左孩子依次入棧
            S.push(cur);
            cur = cur->left;
        }
        //訪問最左孩子
        cur = S.top();
        cout<<""<<cur->data<<"\n";
        S.pop();
        //對右子樹進行一樣的操作
        cur = cur->right;
    }
}

層次遍歷

層次遍歷就是廣度優先遍歷，需要使用隊列的特性FIFO

演算法：

1. 根節點入隊
2. 若隊列非空，出隊一個元素並訪問，接著將其左右孩子入隊
3. 重覆步驟2直至隊空

void levelOrder(BTNode* root) {
    queue<BTNode*> Q;
    if(root == NULL)
        return;
    BTNode* cur = root;
    Q.push(root);
    while(!Q.empty()) {
        //訪問隊首元素
        cur = Q.front();
        cout<<cur->data<<"\n";
        Q.pop();
        /*將左右孩子入隊*/
        if(cur->left != NULL)
            Q.push(cur->left);
        if(cur->right != NULL)
            Q.push(cur->left);
    }
}