二叉樹的重建

2019-11-06 06:01:50

字體：大中小

來源：轉載

供稿：網友

在http://blog.csdn.net/hacker_zhidian/article/details/60586445這篇文章中我們看了一下二叉樹的四種遍歷方式，接下來我們看一下關于二叉樹的重建問題，什么叫二叉樹的重建呢？

比方說給你一棵二叉樹的前序遍歷順序和中序遍歷順序，要求你求出這顆二叉樹的后序遍歷順序。來看一下個具體的例題數據，給定一個二叉樹的信息：

二叉樹節點數： 5 前序遍歷順序：1 2 3 4 5 中序遍歷順序：3 2 4 1 5 求后續遍歷順序？

像這種題目咋一看沒什么頭緒啊，如果不熟悉二叉樹的性質，這種題是挺費腦的。但是我們仔細想想，二叉樹的前序遍歷順序是：根節點 –> 左子樹 –> 右子樹 中序遍歷的順序是：左子樹 –> 根節點 –> 右子樹。

那么從上面的數據中，我們可以知道，節點值為 1 的節點就是整個二叉樹的根節點。之后再去中序遍歷的順序中找節點值為 1 的節點位置，我們在中序遍歷的順序中發現，節點值為 1 的節點右邊有一個節點值為 5 的節點，左邊有三個節點值分別為 3 2 4 的節點。Ok，根據中序遍歷的順序，我們知道節點值為 1 的節點有兩棵子樹，節點值為 1 的節點有兩個子節點，接下來，我們要對這個節點的做右子節點進行討論：前序遍歷的順序的第二個節點（節點值為 2 ）就是節點值為 1 的節點的左子節點，接下來繼續查找這個節點值為 2 的節點在中序遍歷中的位置，我們發現節點值為 2 的節點在中序遍歷中也存在左右子節點，那么繼續對它的左右子節點討論。。。

整個過程的代碼，也是這個問題的核心代碼：

// 重建二叉樹以第 n 個節點為根節點的子二叉樹，l 為二叉樹節點的左邊界，r 為右邊界void rec(int l, int r, int n) { if(l >= r) { node[n].w = INF; // 如果當前節點為空，那么賦值為 INF return ; } int root = PRe[pos++]; node[n].w = root; // 獲取當前節點儲存的值 node[n].l = 2 * n; // 當前節點左孩子所在數組下標 node[n].r = 2 * n + 1; // 當前節點右孩子節點所在數組下標 int m = find(in, in+r, root) - in; // 得到當前節點在中序遍歷數組中的下標 rec(l, m, 2*n); // 重建左子樹 rec(m+1, r, 2*n+1); // 重建右子樹 }

上述代碼中，node儲存的是二叉樹節點的信息數組。下面給出完整的代碼：

/* * 根據二叉樹的前序遍歷和中序遍歷重建二叉樹, * 這里依然采用數組下標來模擬指針 */#include <iostream>#include <algorithm>using namespace std;const int INF = -999999999; // 二叉樹節點為空的時候儲存的數值 const int N = 100010; // 二叉樹的節點個數 int pre[N]; // 二叉樹前序遍歷的結果 int in[N]; // 二叉樹中序遍歷的結果 int pos; struct Node { // 節點信息結構體 int l; // 節點的左孩子所在數組下標 int r; // 節點的右孩子所在數組下標 int w; // 節點的值 }; Node node[N]; // 儲存二叉樹節點信息的數組 // 重建二叉樹的第 n 個節點為根節點的子二叉樹, l 為二叉樹節點的左邊界，r 為右邊界void rec(int l, int r, int n) { if(l >= r) { node[n].w = INF; // 如果當前節點為空，那么賦值為 -1 return ; } int root = pre[pos++]; node[n].w = root; // 獲取當前節點儲存的值 node[n].l = 2 * n; // 當前節點左孩子所在數組下標 node[n].r = 2 * n + 1; // 當前節點右孩子節點所在數組下標 int m = find(in, in+r, root) - in; // 得到當前節點在中序遍歷數組中的下標 rec(l, m, 2*n); // 重建左子樹 rec(m+1, r, 2*n+1); // 重建右子樹 }// 后序遍歷重建的二叉樹 void postOrderParse(int n) { if(node[n].w == INF) { // 如果當前節點為空，那么結束輸出 return ; } postOrderParse(2*n); postOrderParse(2*n+1); // 這里輸出沒有嚴格的控制空格個數，在 OJ 上做題的小伙伴注意一下 cout << node[n].w << " "; } int main() { int n; cin >> n; for(int i = 0; i < n; i++) { cin >> pre[i]; } for(int i = 0; i < n; i++) { cin >> in[i]; } rec(0, n, 1); // 從二叉樹根節點開始重建二叉樹 cout << "該二叉樹的后序遍歷：" << endl; postOrderParse(1); return 0;}

好了。來看一下運行結果：

這里寫圖片描述