二叉樹的建立和周遊

一、基礎

在建立二叉樹之前，我們先來了解一下二叉樹和幾個特殊的二叉樹

首先說一下二叉樹：二叉樹就展現在“二”上，也就是，每一個結點最多隻有兩個子樹，即二叉樹中不存在度大于2的結點；除此之外，二叉樹的兩個子樹有左右之分，也就是左右子樹的順序不能颠倒。那麼我們就可以得出一個結論，二叉樹是一個有序樹。

如下圖，這就是一個二叉樹，我們接下來建立二叉樹就用這個例子，那麼建立之後的各種周遊，當然也都是用這個。

二叉樹的建立和周遊

在二叉樹的分類中有幾個特殊的二叉樹，其中所有分支結點都存在左子樹和右子樹，并且，所有的葉子結點都在同一個層，這樣的二叉樹就是滿二叉樹。

二叉樹的建立和周遊

還有一個比較特殊的，應用也比較多的二叉樹是完全二叉樹，是這樣叙述：如果一棵具有N個結點的二叉樹的結構與滿二叉樹的前N個結點的結構相同，那麼這就是完全二叉樹了，解釋一下，這裡的額前N個結點是說的是，将二叉樹上的結點，按照從上到下，，從左到右的順序編号，後面的層序也是這樣。

二叉樹的建立和周遊

之後我們再來說一下二叉樹的建立，如果要想建立一個二叉樹，那麼你會從哪入手呢？有人想從根結點入手，也有人想從左子樹入手，那麼到底該怎麼進行呢？

在這裡我們總結幾種方法：

先序：根結點——>左子樹——>右子樹

中序：左子樹——>根結點——>右子樹

後序：左子樹——>右子樹——>根結點

層序：從根結點開始，按照從上到下，從左到右的順序

同樣的，二叉樹的周遊也是這幾種方法，那麼接下來我們就來分析一下二叉樹的建立和周遊吧。

二、建立

二叉樹的建立我們用先序的例子來介紹。按照先序的順序，首先應該建立根結點，然後再建立左子樹，然後是右子樹。其中左子樹也是二叉樹，那麼完全可以自己調用自己，也就是遞歸。思路很簡單，那麼接下來就是實作了。

我們想要建立建立二叉樹的結點，首先分析一下，結點有什麼，儲存在這個結點的值是一個吧，還有就是指向兩個子樹的指針也是吧。我們想建立這個結點，那麼可以将構造函數給出來吧。之後将這些封裝到結構體中就行了。

template<class T>
struct BinaryTreeNode
{
    BinaryTreeNode(const T& value)
    : _value(value)
    , _pLeft(NULL)
    , _pRight(NULL)
    {}

    T _value;
    BinaryTreeNode<T>* _pLeft;   // 左孩子
    BinaryTreeNode<T>* _pRight;  // 右孩子
};

之後就是建立這個二叉樹的實作了，前面大緻提了一下這個方法，但是具體怎麼實作呢？

我們用先序建立的順序是“124356”，但是我們就這樣将建立的時候會出現什麼現象呢？這個會一直建立左子樹，最後會建立一個左單支，顯然不是我們想要的，那麼問題出在哪裡呢？

當我們建立124的時候顯然是沒有問題的，但是3是1的右子樹，但是我們建立的時候把3給成4的左子樹了，而4的左子樹本來是沒有的，是以我們得想個辦法處理一下左右子樹為空的時候。

其實很簡單，我們可以将這些避開就行了，可以定義一個invalid，隻要出現是invalid的時候，那麼就跳過直接進行下一步。

如圖：

二叉樹的建立和周遊

那麼我們的數組應該給成：“124###35##6”，然後就是實作了：

//建立二叉樹
    void _CreateBinaryTree(Node* &pRoot, const T array[], size_t size, size_t& index, const T& invalid)
    {
        if (index < size&&array[index] != invalid)
        {
            pRoot = new Node(invalid);//注意new的時候要和結構體中寫的函數參數對應
            pRoot->_value = array[index];

            _CreateBinaryTree(pRoot->_pLeft, array, size, ++index, invalid);//注意：++index
            _CreateBinaryTree(pRoot->_pRight, array, size, ++index, invalid);
        }
    }

周遊其實也是這幾種方法

先序：根結點——>左子樹——>右子樹

中序：左子樹——>根結點——>右子樹

後序：左子樹——>右子樹——>根結點

層序：從根結點開始，按照從上到下，從左到右的順序

首來看先序：

二叉樹的建立和周遊

那麼我們先來将先序的周遊結構寫出來：124356，思路很簡單，先找到根結點，通路，然後再周遊左子樹，最後是右子樹，如果用遞歸的話，這樣差不多就完了，不過，隻是差不多，遞歸出口我們還沒有給出呢。

那麼遞歸出口應該怎麼給呢？我們再來看圖，通路到4的位置，左子樹是不是通路完了，再通路，那麼左子樹就為空了，不能通路，是以，我們可以将pCur判斷一下，隻要其不為空，那麼就可以繼續遞歸，如果它為空，那麼就傳回。

那麼接下來就是将這些思路翻譯成代碼，然後測試一下，看結果是不是“124356”

// 先序：通路根節點--->通路根節點的左子樹--->通路根節點的右子樹
    void _PreOrder(Node* pRoot)   //時間複雜度：
    {
        Node* pCur = pRoot;
        if (pCur == NULL)
            return;

        cout << pCur->_value << " ";

        _PreOrder(pCur->_pLeft);

        _PreOrder(pCur->_pRight);
    }

那麼不用遞歸呢？

再來回顧一下先序的周遊順序：根結點—–左子樹—–右子樹

進入左子樹中還是這樣，直到最後一個結點是空，那麼這個過程是不是可以看成找這個二叉樹的最左邊的結點，并且在找的過程中，将路徑上面的結點全部通路了，之後然後在通路右子樹，但是這時候右子樹怎麼找呢？

我們可以在用棧将要周遊的結點儲存起來，這時候就是展現模闆的強大了，我們需要的是結構體類型的，那麼定義棧的時候隻需将Node*加入執行個體化清單中就行了。

然後再來看我們的思路：

1、首先我們得判斷樹是不是空的，如果是，那麼我們就不需要處理了，return;就行了

2、然後将根結點入棧

3、取出棧頂的元素，通路了，讓其出棧

4、再将這個結點的左子樹和右子樹壓棧，不過要是不存在就不用了，是以還是加一個判斷語句為好。

3、4其實是循環進行的，我們判斷執行下一步的語句就是不斷取出棧頂元素，現在思路寫的差不多了，再來通過這個例子捋一遍：

首先将1壓棧，然後取出1，通路，再将1的左右子樹壓棧，即2、3壓棧，這時候循環，再來去棧頂元素，是3。。。。怎麼是3呢？按理說我們因應該周遊2才對的吧，這時候就不得不提棧的性質了，後進先出，是以将左子樹和右子樹和右子樹的壓棧順序調整一下，先将右子樹壓棧，再将左子樹壓棧

//先序-----(非遞歸)：用棧實作
    void _PreOrder_Nor(Node *pRoot)
    {
        if (pRoot == NULL)
            return;
        stack<Node*> s;
        s.push(pRoot);

        while (!s.empty())
        {
            Node *pCur = s.top();
            cout << pCur->_value << " ";

            s.pop();//時刻記住，通路完後要出棧

            if (pCur->_pRight)//注意，入棧順序是先右後左
                s.push(pCur->_pRight);
            if (pCur->_pLeft)
                s.push(pCur->_pLeft);
        }
    }

中序的周遊和先序的差不多，隻是周遊的順序不同而已，中序是先通路左子樹，再通路根結點，那麼我們将先序周遊的方法中遞歸左子樹和通路根結點兩條語句交換一下就行了。

二叉樹的建立和周遊

// 中序：通路根節點的左子樹--->通路根節點--->通路根節點的右子樹
    void _InOrder(Node* pRoot)
    {
        Node *pCur = pRoot;
        if (pCur == NULL)
            return;

        _InOrder(pCur->_pLeft);

        cout << pCur->_value << " ";

        _InOrder(pCur->_pRight);
    }

同樣的，中序的非遞歸實作方法也是通過棧實作的，那麼這個可不可以像遞歸的形式一樣，将通路根結點和左子樹交換一下呢？

其實，這樣做是沒有毛病的，中序的非遞歸的思路也很簡單：

1、判斷樹是否為空，為空，那麼直接return;

2、将根結點入棧

3、找最左邊的結點，并儲存路徑上的所有結點（注：隻是儲存，不能通路）

4、找到之後，取出棧頂元素，并通路，讓其出棧

5、pCur = pCur->_pRight

第四步我們通路的實際上是根結點，那麼根據中序周遊的順序，我們該通路右子樹了，但是，右子樹的根結點可能不存在，是以，我們在最外層的循環中應該再加一個條件，目前結點不為空的時候才能循環，那麼如果右子樹為空，那麼，就進不去循環，但是現在棧不為空，又可以進入循環，在取棧頂元素進行通路，是以，最外圍新加的條件和原來判斷棧是否為空的條件應該是“||”的關系吧。

//中序（非遞歸）----用棧
    void _InOrder_Nor(Node *pRoot)
    {
        if (pRoot == NULL)
            return;

        stack<Node*> s;
        Node *pCur = pRoot;

        while (pCur || !s.empty())
        {
            //找最左邊的結點，并儲存到棧中
            while (pCur)
            {
                s.push(pCur);
                pCur = pCur->_pLeft;
            }

            //找到最左邊的結點之後，取棧頂元素（根），并通路，後出棧
            pCur = s.top();
            cout << pCur->_value << " ";
            s.pop();

            pCur = pCur->_pRight;//可以分情況讨論
        }
    }

後序也是這樣，将中序的通路根結點和遞歸右子樹交換一下即可

二叉樹的建立和周遊

// 後續周遊：周遊根的左子樹-->周遊根的右子樹-->周遊根節點
    void _PostOrder(Node* pRoot)
    {
        Node *pCur = pRoot;
        if (pCur == NULL)
            return;

        _PostOrder(pCur->_pLeft);

        _PostOrder(pCur->_pRight);

        cout << pCur->_value << " ";
    }

後序的循環實作也是通過棧，步驟和先序中序差不多，不過，具體的實作總是會發現問題的。

我們先來說一下這個思路：

1、判斷樹是否為空，為空，return;

2、儲存根結點到棧中

3、找最左邊的結點，并且将路徑上的結點都儲存。

4、取出棧頂元素，

5、如果右子樹為空或是已經通路過，那麼就可以通路了

由于根結點的通路條件中有一個是右子樹已經通路過，那麼如何判斷已經通路過呢？其實很簡單，隻需在沒通路一個結點的時候将其用一個指針（prev）指向即可，那麼我們在判斷右子樹是否通路過的時候，隻需将指向右子樹的指針和prev比較一下就行了，如果相等，那麼我們就可以通路根結點了。

//後序（非遞歸）----用棧
    void _PostOrder_Nor(Node * pRoot)
    {
        if (pRoot == NULL)
            return;

        stack<Node*> s;
        Node* pCur = pRoot;
        Node*prev = NULL;//用來指向最新一次通路的結點

        while (pCur||!s.empty())
        {
            while (pCur)
            {
                s.push(pCur);
                pCur = pCur->_pLeft;
            }

            Node* pTop = s.top();

            //通路根結點---->右為空 或者 右已經通路過了
            if (pTop->_pRight == NULL || pTop->_pRight == prev)
            {
                cout << pTop->_value << " ";
                prev = pTop;//将最新通路過的結點儲存
                s.pop();
            }
            else
                pCur = pTop->_pRight;
        }
    }

層序的通路順序是從上到下，從左到右的，按照我們的例子來說是1，2，3，4，5，6

其中1是一層，2，3是一層，并且是1的左右孩子；同樣，4，是2的左孩子，5，6是3的左右孩子。

那麼我們就可以想一下，是不是可以将1儲存，再将1的左右子樹儲存，之後再通路1；然後再儲存2的左右子樹（如果存在的話），通路2；再通路3的左右子樹，通路3；再循環下去的話，是該2的左子樹了……

如此，一邊儲存，一邊取出通路，會聯想起什麼呢？

沒錯，就是隊列，應用隊列，我們再來捋一遍思路：

1、判斷樹是不是空樹：是，return;

2、将根結點放入隊列

3、取出隊頭元素，将其左右孩子存入隊列（判斷孩子是否存在）

4、通路目前結點，之後讓其出隊列

3、4這兩個步驟其實是循環進行的，其中循環的執行流就是不斷地取對頭元素，直到隊列為空停止。

//層序-----用隊列實作
    void _LevelOrder(Node *pRoot)
    {
        if (pRoot == NULL)
            return;
        queue<Node *> q;
        q.push(pRoot);//先将根結點放入隊列

        while (!q.empty())
        {
            Node* pCur = q.front();//取隊頭元素，将其存在的左右孩子放入隊列
            if (pCur->_pLeft)
                q.push(pCur->_pLeft);
            if (pCur->_pRight)
                q.push(pCur->_pRight);

            cout << pCur->_value << " ";//通路目前結點
            q.pop();//将通路過的結點出隊列
        }
    }

下面是具體的實作代碼，包括拷貝構造函數和指派運算符重載：

不過如果你的具體代碼不想讓别人知道的話，可以将代碼在封裝一層，将具體的實作代碼寫在private

#include<iostream>
using namespace std;

#include<queue>
#include<stack>

// 孩子表示法
template<class T>
struct BinaryTreeNode
{
    BinaryTreeNode(const T& value)
    : _value(value)
    , _pLeft(NULL)
    , _pRight(NULL)
    {}

    T _value;
    BinaryTreeNode<T>* _pLeft;   // 左孩子
    BinaryTreeNode<T>* _pRight;  // 右孩子
};


template<class T>
class BinaryTree
{
    typedef BinaryTreeNode<T> Node;//換個名字Node
public:
    //構造函數①
    BinaryTree()
        :_pRoot(NULL)
    {}

    //構造函數②
    BinaryTree(const T array[], size_t size, const T& invalid)
    {
        size_t index = ;
        _CreateBinaryTree(_pRoot, array, size, index, invalid);
    }

    //拷貝構造函數
    BinaryTree(const BinaryTree<T>& bt)
    {
        _pRoot = _CopyBirnaryTree(bt._pRoot);
    }

    //指派運算符重載
    BinaryTree<T>& operator=(const BinaryTree<T>& bt)
    {
        if (this != &bt)
        {
            _CopyBirnaryTree(bt._pRoot);
        }
        return this;
    }

    //析構函數
    ~BinaryTree()
    {
        _DestroyBinaryTree(_pRoot);
    }


    //先序周遊
    void PreOrder()
    {
        cout << "PreOrder:" << endl;
        _PreOrder(_pRoot);
        cout << endl;
    }

    先序周遊（非遞歸）
    void PreOrder_Nor()
    {
        cout << "PreOrder_Nor:" << endl;
        _PreOrder_Nor(_pRoot);
        cout << endl;
    }

    //中序周遊
    void InOrder()
    {
        cout << "InOrder:" << endl;
        _InOrder(_pRoot);
        cout << endl;
    }

    // 中序周遊（非遞歸）。哪一種快？
    void InOrder_Nor()
    {
        cout << "InOrder_Nor:" << endl;
        _InOrder_Nor(_pRoot);
        cout << endl;
    }

    //後序周遊
    void PostOrder()
    {
        cout << "PostOrder:" << endl;
        _PostOrder(_pRoot);
        cout << endl;
    }

    //後序周遊（非遞歸）
    void PostOrder_Nor()
    {
        cout << "PostOrder:" << endl;
        _PostOrder_Nor(_pRoot);
        cout << endl;
    }

    // 層序周遊
    void LevelOrder()
    {
        cout << "LevelOrder:" << endl;
        _LevelOrder(_pRoot);
    }

private:
    //建立二叉樹
    void _CreateBinaryTree(Node* &pRoot, const T array[], size_t size, size_t& index, const T& invalid)
    {
        if (index < size&&array[index] != invalid)
        {
            pRoot = new Node(invalid);//注意new的時候要和結構體中寫的函數參數對應
            pRoot->_value = array[index];

            _CreateBinaryTree(pRoot->_pLeft, array, size, ++index, invalid);//注意：++index
            _CreateBinaryTree(pRoot->_pRight, array, size, ++index, invalid);
        }
    }

    // pRoot-->被拷貝樹的根節點
    Node* _CopyBirnaryTree(Node* pRoot)
    {
        if (pRoot == NULL)
            return NULL;
        Node *NewRoot = new Node(pRoot->_value);
        NewRoot->_pLeft = _CopyBirnaryTree(pRoot->_pLeft);
        NewRoot->_pRight = _CopyBirnaryTree(pRoot->_pRight);
        return NewRoot;
    }

    //銷毀二叉樹
    void _DestroyBinaryTree(Node*& pRoot)
    {
        Node* temp = pRoot;
        if (temp == NULL)
            return;
        _DestroyBinaryTree(temp->_pLeft);
        _DestroyBinaryTree(temp->_pRight);
        delete temp;
        temp = NULL;
    }


    // 先序：通路根節點--->通路根節點的左子樹--->通路根節點的右子樹
    void _PreOrder(Node* pRoot)   //時間複雜度：
    {
        Node* pCur = pRoot;
        if (pCur == NULL)
            return;

        cout << pCur->_value << " ";

        _PreOrder(pCur->_pLeft);

        _PreOrder(pCur->_pRight);
    }

    //先序-----(非遞歸)：用棧實作
    void _PreOrder_Nor(Node *pRoot)
    {
        if (pRoot == NULL)
            return;
        stack<Node*> s;
        s.push(pRoot);

        while (!s.empty())
        {
            Node *pCur = s.top();
            cout << pCur->_value << " ";

            s.pop();//時刻記住，通路完後要出棧

            if (pCur->_pRight)//注意，入棧順序是先右後左
                s.push(pCur->_pRight);
            if (pCur->_pLeft)
                s.push(pCur->_pLeft);
        }
    }

    // 中序：通路根節點的左子樹--->通路根節點--->通路根節點的右子樹
    void _InOrder(Node* pRoot)
    {
        Node *pCur = pRoot;
        if (pCur == NULL)
            return;

        _InOrder(pCur->_pLeft);

        cout << pCur->_value << " ";

        _InOrder(pCur->_pRight);
    }

    //中序（非遞歸）----用棧
    void _InOrder_Nor(Node *pRoot)
    {
        if (pRoot == NULL)
            return;

        stack<Node*> s;
        Node *pCur = pRoot;

        while (pCur || !s.empty())
        {
            //找最左邊的結點，并儲存到棧中
            while (pCur)
            {
                s.push(pCur);
                pCur = pCur->_pLeft;
            }

            //找到最左邊的結點之後，取棧頂元素（根），并通路，後出棧
            pCur = s.top();
            cout << pCur->_value << " ";
            s.pop();

            pCur = pCur->_pRight;//可以分情況讨論
        }
    }

    // 後續周遊：周遊根的左子樹-->周遊根的右子樹-->周遊根節點
    void _PostOrder(Node* pRoot)
    {
        Node *pCur = pRoot;
        if (pCur == NULL)
            return;

        _PostOrder(pCur->_pLeft);

        _PostOrder(pCur->_pRight);

        cout << pCur->_value << " ";
    }

    //後序（非遞歸）----用棧
    void _PostOrder_Nor(Node * pRoot)
    {
        if (pRoot == NULL)
            return;

        stack<Node*> s;
        Node* pCur = pRoot;
        Node*prev = NULL;//用來指向最新一次通路的結點

        while (pCur||!s.empty())
        {
            while (pCur)
            {
                s.push(pCur);
                pCur = pCur->_pLeft;
            }

            Node* pTop = s.top();

            //通路根結點---->右為空 或者 右已經通路過了
            if (pTop->_pRight == NULL || pTop->_pRight == prev)
            {
                cout << pTop->_value << " ";
                prev = pTop;//将最新通路過的結點儲存
                s.pop();
            }
            else
                pCur = pTop->_pRight;
        }
    }

    //層序-----用隊列實作
    void _LevelOrder(Node *pRoot)
    {
        if (pRoot == NULL)
            return;
        queue<Node *> q;
        q.push(pRoot);//先将根結點放入隊列

        while (!q.empty())
        {
            Node* pCur = q.front();//取隊頭元素，将其存在的左右孩子放入隊列
            if (pCur->_pLeft)
                q.push(pCur->_pLeft);
            if (pCur->_pRight)
                q.push(pCur->_pRight);

            cout << pCur->_value << " ";//通路目前結點
            q.pop();//将通路過的結點出隊列
        }
    }

private:
    Node* _pRoot;   // 指向樹的根節點
};


void FunTest()
{
    char* pStr = "124###35##6";

    BinaryTree<char> bt(pStr, strlen(pStr), '#');
    //bt.PreOrder();
    //bt.InOrder();
    //bt.PostOrder();
    //bt.LevelOrder();

//  BinaryTree<char> bt1(bt);
//  bt1.PreOrder();
//  bt1.InOrder();
//  bt1.PostOrder();
//
//  BinaryTree<char> bt2;
//  bt2 = bt1;
//  bt2.PostOrder();

    bt.PreOrder_Nor();
    bt.InOrder_Nor();
    bt.PostOrder_Nor();
}


int main()
{
    FunTest();
    return ;
}

結果：

二叉樹的建立和周遊

二叉樹的建立和周遊

一、基礎

二、建立

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器