在http://blog.csdn.net/hacker_zhidian/article/details/60586445這篇文章中我們看了一下二叉樹的四種遍歷方式，接下來(lái)我們看一下關(guān)于二叉樹的重建問題，什么叫二叉樹的重建呢？
比方說給你一棵二叉樹的前序遍歷順序和中序遍歷順序，要求你求出這顆二叉樹的后序遍歷順序。來(lái)看一下個(gè)具體的例題數(shù)據(jù)，給定一個(gè)二叉樹的信息：
二叉樹節(jié)點(diǎn)數(shù)： 5 前序遍歷順序：1 2 3 4 5 中序遍歷順序：3 2 4 1 5 求后續(xù)遍歷順序？
像這種題目咋一看沒什么頭緒啊，如果不熟悉二叉樹的性質(zhì)，這種題是挺費(fèi)腦的。但是我們仔細(xì)想想，二叉樹的前序遍歷順序是：根節(jié)點(diǎn) –> 左子樹 –> 右子樹 中序遍歷的順序是：左子樹 –> 根節(jié)點(diǎn) –> 右子樹。
那么從上面的數(shù)據(jù)中，我們可以知道，節(jié)點(diǎn)值為 1 的節(jié)點(diǎn)就是整個(gè)二叉樹的根節(jié)點(diǎn)。之后再去中序遍歷的順序中找節(jié)點(diǎn)值為 1 的節(jié)點(diǎn)位置，我們?cè)谥行虮闅v的順序中發(fā)現(xiàn)， 節(jié)點(diǎn)值為 1 的節(jié)點(diǎn)右邊有一個(gè)節(jié)點(diǎn)值為 5 的節(jié)點(diǎn)，左邊有三個(gè)節(jié)點(diǎn)值分別為 3 2 4 的節(jié)點(diǎn)。Ok，根據(jù)中序遍歷的順序，我們知道節(jié)點(diǎn)值為 1 的節(jié)點(diǎn)有兩棵子樹，節(jié)點(diǎn)值為 1 的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，接下來(lái)，我們要對(duì)這個(gè)節(jié)點(diǎn)的做右子節(jié)點(diǎn)進(jìn)行討論：前序遍歷的順序的第二個(gè)節(jié)點(diǎn)（節(jié)點(diǎn)值為 2 ）就是節(jié)點(diǎn)值為 1 的節(jié)點(diǎn)的左子節(jié)點(diǎn)，接下來(lái)繼續(xù)查找這個(gè)節(jié)點(diǎn)值為 2 的節(jié)點(diǎn)在中序遍歷中的位置，我們發(fā)現(xiàn)節(jié)點(diǎn)值為 2 的節(jié)點(diǎn)在中序遍歷中也存在左右子節(jié)點(diǎn)，那么繼續(xù)對(duì)它的左右子節(jié)點(diǎn)討論。。。
整個(gè)過程的代碼，也是這個(gè)問題的核心代碼：
// 重建二叉樹以第 n 個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的子二叉樹，l 為二叉樹節(jié)點(diǎn)的左邊界，r 為右邊界void rec(int l, int r, int n) { if(l >= r) { node[n].w = INF; // 如果當(dāng)前節(jié)點(diǎn)為空，那么賦值為 INF return ; } int root = PRe[pos++]; node[n].w = root; // 獲取當(dāng)前節(jié)點(diǎn)儲(chǔ)存的值 node[n].l = 2 * n; // 當(dāng)前節(jié)點(diǎn)左孩子所在數(shù)組下標(biāo) node[n].r = 2 * n + 1; // 當(dāng)前節(jié)點(diǎn)右孩子節(jié)點(diǎn)所在數(shù)組下標(biāo) int m = find(in, in+r, root) - in; // 得到當(dāng)前節(jié)點(diǎn)在中序遍歷數(shù)組中的下標(biāo) rec(l, m, 2*n); // 重建左子樹 rec(m+1, r, 2*n+1); // 重建右子樹 }上述代碼中，node儲(chǔ)存的是二叉樹節(jié)點(diǎn)的信息數(shù)組。下面給出完整的代碼：
/* * 根據(jù)二叉樹的前序遍歷和中序遍歷重建二叉樹, * 這里依然采用數(shù)組下標(biāo)來(lái)模擬指針 */#include <iostream>#include <algorithm>using namespace std;const int INF = -999999999; // 二叉樹節(jié)點(diǎn)為空的時(shí)候儲(chǔ)存的數(shù)值 const int N = 100010; // 二叉樹的節(jié)點(diǎn)個(gè)數(shù) int pre[N]; // 二叉樹前序遍歷的結(jié)果 int in[N]; // 二叉樹中序遍歷的結(jié)果 int pos; struct Node { // 節(jié)點(diǎn)信息結(jié)構(gòu)體 int l; // 節(jié)點(diǎn)的左孩子所在數(shù)組下標(biāo) int r; // 節(jié)點(diǎn)的右孩子所在數(shù)組下標(biāo) int w; // 節(jié)點(diǎn)的值 }; Node node[N]; // 儲(chǔ)存二叉樹節(jié)點(diǎn)信息的數(shù)組 // 重建二叉樹的第 n 個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的子二叉樹, l 為二叉樹節(jié)點(diǎn)的左邊界，r 為右邊界void rec(int l, int r, int n) { if(l >= r) { node[n].w = INF; // 如果當(dāng)前節(jié)點(diǎn)為空，那么賦值為 -1 return ; } int root = pre[pos++]; node[n].w = root; // 獲取當(dāng)前節(jié)點(diǎn)儲(chǔ)存的值 node[n].l = 2 * n; // 當(dāng)前節(jié)點(diǎn)左孩子所在數(shù)組下標(biāo) node[n].r = 2 * n + 1; // 當(dāng)前節(jié)點(diǎn)右孩子節(jié)點(diǎn)所在數(shù)組下標(biāo) int m = find(in, in+r, root) - in; // 得到當(dāng)前節(jié)點(diǎn)在中序遍歷數(shù)組中的下標(biāo) rec(l, m, 2*n); // 重建左子樹 rec(m+1, r, 2*n+1); // 重建右子樹 }// 后序遍歷重建的二叉樹 void postOrderParse(int n) { if(node[n].w == INF) { // 如果當(dāng)前節(jié)點(diǎn)為空，那么結(jié)束輸出 return ; } postOrderParse(2*n); postOrderParse(2*n+1); // 這里輸出沒有嚴(yán)格的控制空格個(gè)數(shù)，在 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); // 從二叉樹根節(jié)點(diǎn)開始重建二叉樹 cout << "該二叉樹的后序遍歷：" << endl; postOrderParse(1); return 0;}好了。來(lái)看一下運(yùn)行結(jié)果：
我們可以手工構(gòu)造出這棵二叉樹：
根據(jù)二叉樹的遍歷順序，我們可以很容易得到該二叉樹的后續(xù)遍歷，和程序執(zhí)行的結(jié)果一樣。這種二叉樹重建的思想可以解決一類問題，感興趣的小伙伴可以看一下這篇文章 http://blog.csdn.net/Hacker_ZhiDian/article/details/60771795。
或者試一下這道題https://www.patest.cn/contests/gplt/L2-011
好了，如果博客中有什么不正確的地方，還請(qǐng)多多指點(diǎn)。如果覺得我寫得不錯(cuò)，請(qǐng)點(diǎn)個(gè)贊表示對(duì)我的支持。
謝謝觀看。。。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
