二叉樹的前序、中序、后序遍歷的遞回版本非常好理解，在這里就不在贅述了，這里主要講迭代版本，

事實上，計算機在進行遞回呼叫時，會隱式的維護一個堆疊（叫做呼叫堆疊，Call Stack），
呼叫函式就把區域變數、入參、回傳地址（合起來叫做堆疊幀，Stack Frame）一同入堆疊，從函式回傳就出堆疊，
而迭代版本其實就是把這個程序顯式的表現出來，手動的去維護這個堆疊，
同時，迭代版本只需要把節點指標入堆疊出堆疊，占用的空間也會小一些，

前序遍歷

因為前序遍歷的遞回版本是所謂的“尾遞回”（即遞回呼叫發生在函式體的尾部），將尾遞回轉換為迭代相對容易一些：

void postOrder(TreeNode *root)
{
    // 如果根節點為空，直接回傳，
    if (root == nullptr)
        return;

    // 先讓根節點入堆疊
    stack<TreeNode *> nodeStack;
    nodeStack.push(root);

    TreeNode *current;

    while (!nodeStack.empty())
    {
        // 訪問堆疊頂節點，然后馬上彈出
        current = nodeStack.top();
        cout << current->data << endl;
        nodeStack.pop();

        // 因為堆疊有先進后出（FILO）的特性，
        // 所以為了能夠先遍歷左子樹后遍歷右子樹，
        // 就要先把右子節點入堆疊再把左子節點入堆疊，
        // 這樣堆疊頂元素就是左子節點，而左子樹遍歷完彈出后堆疊頂元素就是右子節點了
        if (current->right)
            nodeStack.push(current->right);
        if (current->left)
            nodeStack.push(current->left);
    }
}

然而，這種方法并不容易推廣到中序和后序遍歷，因為中序遍歷不是完全的尾遞回，而后序遍歷甚至都掛不了尾遞回這個名號，因此我們要尋找一種更具一般性的方法，

我們不妨引入一個概念叫做“左側鏈”（Left Chain），一棵二叉樹的左側鏈指的是由根節點一直不斷往左走所形成的節點鏈條，那么，一顆二叉樹就可以看做是這樣的一個結構：

那么，前序遍歷就等價于從上往下依次訪問左側鏈上的每一個節點，然后從下往上依次遍歷這些節點的右子樹，

我們所要做的，就是沿著左側鏈下行，每遍歷到一個節點就讓其右子節點入堆疊，
走完之后，左側鏈的最底層的節點的右子節點，也就是最底層的右子樹的樹根就成了堆疊頂元素，會最先被取出來；
而根節點的右子節點，也就是最頂層的右子樹就成了堆疊底元素，最后才會被取出來，

代碼：

// 假設current最初指向根節點
for (; current != nullptr; current = current->left)
{
    cout << current->data << endl;
    nodeStack.push(current->right);
}

螢屏前的你可能應該想到了，萬一左側鏈上某個節點沒有右子節點（即右子節點為nullptr）呢？也要入堆疊嗎？我們稍后會處理，

沿著左側鏈走完之后，我們只需要重復的進行以下作業：

1. 訪問堆疊頂元素，然后存盤到一個臨時變數，馬上彈出
2. 如果堆疊變空了，那就直接退出，
3. 否則的話，對以臨時變數為根節點的子樹做上述作業（即沿著以該節點為根節點的左側鏈一直向下走，邊走邊把右子樹入堆疊），這其實是在遍歷整棵樹的左側鏈上某一個節點的右子樹，

完整代碼：

void preOrder(TreeNode *root)
{
    TreeNode *current = root;
    stack<TreeNode *> nodeStack;
    while (true)
    {
        // 先從上往下訪問左側鏈上的每一個節點
        for (; current != nullptr; current = current->left)
        {
            cout << current->data << endl;
            nodeStack.push(current->right);
        }

        // 如果堆疊變空了，那就說明所有節點都已經遍歷過了，那就結束
        if (nodeStack.empty())
            break;

        // 遍歷以堆疊頂元素為樹根的子樹
        current = nodeStack.top();
        nodeStack.pop();
    }
}

這時候你應該發現了，如果current取得的是nullptr，根本就不會進入下一次while回圈中的for回圈，馬上就被彈出了，只不過是走了個過場而已，根本不會存在空指標安全問題，

小tips：可能你還不太能理解，覺得過于抽象，沒關系，拿出紙筆，把整個程序畫一畫，你就應該清楚了，

中序遍歷

中序遍歷的程序等價于自下而上訪問左側鏈上的每一個節點并遍歷該節點的右子樹，

你應該想到了，還是用堆疊這種資料結構，來存盤左側鏈上的每一個節點，

要沿著左側鏈一直走下去，邊走邊把節點入堆疊的代碼：

// 假設current最初指向根節點
for (; current != nullptr; current = current->left)
{
    nodeStack.push(current);
}

完整代碼：

```cpp
void inOrder(TreeNode *root)
{
    stack<TreeNode *> nodeStack;
    TreeNode *current = root;
    while (true)
    {
        // 把左側鏈上的所有節點全部入堆疊
        for (; current != nullptr; current = current->left)
        {
            nodeStack.push(current);
        }

        // 如果堆疊變空了，那就說明所有節點都已經遍歷過了，那就結束
        if (nodeStack.empty())
            break;

        // 訪問堆疊頂元素，然后隨即彈出
        current = nodeStack.top();
        nodeStack.pop();
        cout << current->data << endl;

        // 遍歷以該節點的右子節點為樹根的子樹
        current = current->right;
    }
}

后序遍歷

整個程序等價于：

咱們再來引入一個概念叫“左側藤蔓(wàn)”（Left Vine），指：沿著左子節點一直走下去，如果沒有左子節點那就走到右子節點處，直到走到葉節點，這樣形成的一條路徑，

那么整個后序遍歷的程序等價于這樣：

首先，沿著左側藤蔓走，邊走邊把要訪問的節點入堆疊，

// 假設current最初指向根節點
for (current = nodeStack.top(); current != nullptr; current = nodeStack.top())
{
    // 如果有左子節點的話
    if (current->left != nullptr)
    {
        // 如果有右子節點的話先把右子節點入堆疊
        if (current->right != nullptr)
        {
            nodeStack.push(current->right);
        }
        // 然后再把左子節點入堆疊，然后再往左走
        nodeStack.push(current->left);
        current = current->left;
    }
    // 否則就往右走
    else
    {
        nodeStack.push(current->right);
        current = current->right;
    }
}
// 堆疊頂元素是葉子節點的右子節點即nullptr，所以還要進行一次出堆疊操作
nodeStack.pop();

一輪訪問過后，當前節點要么是堆疊頂元素的子節點，要么是堆疊頂元素的兄弟節點，

• 如果當前節點要么是堆疊頂元素的子節點的話，那就說明要往上回溯回去，直接訪問并出堆疊，
• 如果當前節點是堆疊頂元素的兄弟節點，那么就說明要遍歷以兄弟節點為根節點的子樹，為了能夠進入子樹，先要把當前節點設為兄弟節點，

完整代碼：

void postOrder(TreeNode *root)
{
    if (root == nullptr)
        return {};
    stack<TreeNode *> nodeStack;
    TreeNode *current = root;
    nodeStack.push(root); // 先讓根節點入堆疊，確保最后能被訪問到
    while (!nodeStack.empty())
    {
        // 如果當前節點不是堆疊頂元素的子節點而是兄弟節點的話，那就沿著以堆疊頂元素為根節點的子樹的左側藤蔓一直走下去，邊走邊入堆疊
        if (current != nodeStack.top()->left && current != nodeStack.top()->right)
        {
            for (current = nodeStack.top(); current != nullptr; current = nodeStack.top())
            {
                if (current->left != nullptr)
                {
                    if (current->right != nullptr)
                    {
                        nodeStack.push(current->right);
                    }
                    nodeStack.push(current->left);
                }
                else
                {
                    nodeStack.push(current->right);
                }
            }
            nodeStack.pop();
        }
        // 此時堆疊頂元素為左側藤蔓的最底端的節點
        current = nodeStack.top();
        cout << current->data << endl;
        nodeStack.pop();
    }
}

標籤：其他

上一篇：LeetCode - 陣列的旋轉總結

下一篇：分布式存盤系統之Ceph集群部署