Contents

前言四種遍歷樹的方法簡介簡介兩種快速獲得遍歷結(jié)果的方法根據(jù)前序遍歷和后續(xù)遍歷創(chuàng)建樹代碼實現(xiàn)四種遍歷樹的方法的代碼

不說廢話了，下面講講如何根據(jù)pre_order和in_order創(chuàng)建二叉樹。

四種遍歷樹的方法簡介

簡介

首先這里簡單介紹一下二叉樹的4種遍歷方式：

• 前序遍歷（pre_order）

• 中序遍歷（in_order）

• 后序遍歷（post_order）

• 層序遍歷（level_order）

至于這些遍歷的代碼放在文章的最后。

前序遍歷就是先對當(dāng)前的根節(jié)點進(jìn)行操作，然后到左子節(jié)點，再到右子節(jié)點！

中序遍歷就是先對當(dāng)前左子節(jié)點進(jìn)行操作，然后到當(dāng)前根節(jié)點，再到右子節(jié)點！

后序遍歷就是先對當(dāng)前左子節(jié)點進(jìn)行操作，然后到右子節(jié)點，再到當(dāng)前根節(jié)點！

層序遍歷就是按照從上到下從左到右的順序?qū)γ總€節(jié)點進(jìn)行操作！代碼寫起來比前三個復(fù)雜點，得借助隊列，并用迭代的方式來做。

如下圖(之前上課做的筆記)：

兩種快速獲得遍歷結(jié)果的方法

另外，介紹兩個 可以快速地 根據(jù)樹的形狀 得出 前序、后序、中序 的遍歷結(jié)果。

法一：

法二：

根據(jù)前序遍歷和后續(xù)遍歷創(chuàng)建樹

給你一個數(shù)組，用這個數(shù)組的值來創(chuàng)建一個樹，結(jié)果有多種可能：

其中n是數(shù)組中元素的個數(shù)！

但是，如果我們給了兩個數(shù)組，分別是前序遍歷和后續(xù)遍歷的結(jié)果，那么我們就能創(chuàng)建唯一的一個樹！

Note：要求數(shù)組中的元素不重復(fù)，是唯一的！

看過上面對樹的那幾種遍歷方式后，可以發(fā)現(xiàn)：

Note：下面的這個過程有點枯燥，我表述地也不太好，可以看后面的圖。

• 前序遍歷的第一個元素就是樹的根節(jié)點；第二個元素是根節(jié)點的左子節(jié)點，這個左子節(jié)點也是后面的根節(jié)點；

• 根節(jié)點把中序遍歷的數(shù)組一分為二，中序遍歷的數(shù)組中：根節(jié)點的左邊是左樹，根節(jié)點的右邊是右樹

• 

• 所以，我們就對前序遍歷的數(shù)組進(jìn)行遍歷，當(dāng)前索引記為pre_i，在每次遍歷中，到中序遍歷的數(shù)組中找這個pre_i對應(yīng)的值，用這個pre_i把中序遍歷的結(jié)果一分為二。這樣往復(fù)下去就能還原樹了。

下面我畫一下整個流程：

大概就是這樣，不斷地對中序遍歷的數(shù)組一分為二（根據(jù)前序遍歷的數(shù)組的當(dāng)前元素進(jìn)行分割）；中序遍歷的數(shù)組的當(dāng)前元素就是當(dāng)前的根節(jié)點。

代碼實現(xiàn)

先定義樹的節(jié)點：

template 
struct Node{
    T val;
    Node* left;
    Node* right;

    explicit Node(T v) : val(v), left(nullptr), right(nullptr){}
};

根據(jù)前序遍歷和中序遍歷創(chuàng)建樹：

/**
 * @brief 根據(jù)前序遍歷和中序遍歷創(chuàng)建樹
 * @param[in] pre_vec   前序遍歷的數(shù)組
 * @param[in] in_vec    中序遍歷的數(shù)組
 * @param[in] left_in   中序遍歷當(dāng)前段的左邊界
 * @param[in] right_in  中序遍歷當(dāng)前段的右邊界（超尾）
 * @static pre_i        前序遍歷的當(dāng)前的索引
 *
 * @note 在每一層遞歸中，當(dāng)前的 中序遍歷 數(shù)組段 被分為：[left_in, pre_i), pre_i, [pre_i+1, right_in)
 * */
template 
Node* CreateTreeR(vector& pre_vec, vector& in_vec, int left_in, int right_in)
{
    static int pre_i = 0;

    if (left_in < right_in)
    {
        /// 從 前序遍歷 的數(shù)組中 獲取 當(dāng)前 根節(jié)點！
        T cur_root_val = pre_vec.at(pre_i);
        auto* cur_root = new Node(cur_root_val);

        /// 遍歷 中序遍歷 的數(shù)組，找到當(dāng)前根節(jié)點對應(yīng)的索引
        int i = left_in;
        while (i < right_in && cur_root_val != in_vec.at(i)) ++i;

        /// 下次遞歸前 pre_i 是需要向后移動一位的
        ++pre_i;

        /// 一分為二！(注意，i是當(dāng)前節(jié)點的索引哦！)
        cur_root->left  = CreateTreeR(pre_vec, in_vec, left_in, i);              /// 左樹
        cur_root->right = CreateTreeR(pre_vec, in_vec, i+1, right_in);   /// 右樹

        return cur_root;
    }

    /// 當(dāng)分到只剩最后一個元素時就返回空了
    return nullptr;
}

測試這段程序

對創(chuàng)建出來的這個樹，用四種遍歷方法分別遍歷一下子，四種遍歷的代碼在文末。

上面這個是數(shù)字的，我現(xiàn)在拿字符串的試試：

四種遍歷樹的方法的代碼

1.層序遍歷：

/**
 * @brief 樹的層序遍歷
 * */
 template
 void LevelOrder(Node* root, vector& vec)
{
     /// 如果根節(jié)點為空就直接返回
     if (!root) return;

     /// 定義一個隊列放所有可能會成為 "根節(jié)點" 的節(jié)點（每次循環(huán)中都會pop出一個 "根節(jié)點" ）
     queue< Node* > q;
     q.push(root);

     while (!q.empty())
     {
         /// 從隊列中拿出最前面的根節(jié)點
         Node* cur_root = q.front();  /// 這個變量在while外面聲明更好，不用每次都創(chuàng)建一個新變量。
         q.pop();
         /// 保存當(dāng)前 "根節(jié)點" 的值
         vec.push_back(cur_root->val);

         /// 如果左子節(jié)點非空就把左子節(jié)點放入隊列
         if (cur_root->left)
             q.push(cur_root->left);

         /// 如果右子節(jié)點非空就把右子節(jié)點放入隊列
         if (cur_root->right)
             q.push(cur_root->right);
     }
}

2.前序遍歷：

/**
 * @brief 樹的前序遍歷
 * */
template
void PreOrder(Node* root, vector& vec)
{
    if (root)
    {
        vec.push_back(root->val);
        PreOrder(root->left, vec);
        PreOrder(root->right, vec);
    }
}

3.中序遍歷：

/**
 * @brief 樹的中序遍歷
 * */
template
void InOrder(Node* root, vector& vec)
{
    if (root)
    {
        InOrder(root->left, vec);
        vec.push_back(root->val);
        InOrder(root->right, vec);
    }
}

4.后序遍歷：

/**
 * @brief 樹的后序遍歷
 * */
template
void PostOrder(Node* root, vector& vec)
{
    if (root)
    {
        PostOrder(root->left, vec);
        PostOrder(root->right, vec);
        vec.push_back(root->val);
    }
}