知道前序遍歷，中序遍歷怎么求后序遍歷？分析過(guò)程：以下面的例子說(shuō)明：已知二叉樹(shù)的前序遍歷序列和中序遍歷序列分別為abdgcefh和dgbaechf，求二叉樹(shù)和后序遍歷序列。分析：前序遍歷序列的第一個(gè)特征

知道前序遍歷，中序遍歷怎么求后序遍歷？

分析過(guò)程：以下面的例子說(shuō)明：已知二叉樹(shù)的前序遍歷序列和中序遍歷序列分別為abdgcefh和dgbaechf，求二叉樹(shù)和后序遍歷序列。分析：前序遍歷序列的第一個(gè)特征是根節(jié)點(diǎn)。對(duì)于中間順序遍歷，根節(jié)點(diǎn)位于中間順序遍歷序列的中間，左部分為根節(jié)點(diǎn)左子樹(shù)的中間順序遍歷序列，右部分為根節(jié)點(diǎn)右子樹(shù)的中間順序遍歷序列。一階：abdgcefh-->abdgcefh中間階：dgbaechf-->dgbaechf得出結(jié)論：a是樹(shù)的根，a有左子樹(shù)和右子樹(shù)，左子樹(shù)有BDG節(jié)點(diǎn)，右子樹(shù)有CEFH節(jié)點(diǎn)。一階：BDG-->bdg中間階：DGB-->dgb得出結(jié)論：B是左子樹(shù)的根節(jié)點(diǎn)，B沒(méi)有右子樹(shù)，但有左子樹(shù)。一階：DG-->dg中間階：DG-->dg得出結(jié)論：D是B的左子樹(shù)的根，D沒(méi)有左子樹(shù)，但有右子樹(shù)。一階：CEFH-->cefh中間階：echf-->echf得出結(jié)論：C是右子樹(shù)的根節(jié)點(diǎn)，C有左子樹(shù)（只有e節(jié)點(diǎn)），右子樹(shù)（有FH節(jié)點(diǎn)）。一階：FH-->fh中間階：HF-->F得出結(jié)論：F是C的左子樹(shù)的根，F(xiàn)有左子樹(shù)（只有h節(jié)點(diǎn)），沒(méi)有右子樹(shù)。將二叉樹(shù)還原為：cdefgh后序遍歷順序：gdbehfca

首先，前序、中序、后序的遍歷順序要明確：前序：父節(jié)點(diǎn)、左子節(jié)點(diǎn)、右子節(jié)點(diǎn)；中序：左子節(jié)點(diǎn)、父節(jié)點(diǎn)、右子節(jié)點(diǎn)；后序：左子節(jié)點(diǎn)、右子節(jié)點(diǎn)，父節(jié)點(diǎn)；后序：左子節(jié)點(diǎn)，右子節(jié)點(diǎn)；后序：左子節(jié)點(diǎn)，右子節(jié)點(diǎn)；后序：左子節(jié)點(diǎn)，右子節(jié)點(diǎn)；后序：左子節(jié)點(diǎn)，右子節(jié)點(diǎn)；首先根據(jù)前序遍歷，確定整個(gè)二叉樹(shù)的根節(jié)點(diǎn)（前序的第一個(gè)節(jié)點(diǎn)）；然后通過(guò)中間節(jié)點(diǎn)順序遍歷，整個(gè)二叉樹(shù)可以根據(jù)根節(jié)點(diǎn)直接劃分為兩個(gè)子樹(shù)。

此時(shí)，按照預(yù)序和中間序一步一步地繪制整個(gè)二叉樹(shù)并不困難。然后我們可以編寫(xiě)后序遍歷序列。例如：已知二叉樹(shù)的前序遍歷序列為bc D E F H，中序遍歷序列為bd C E a H F，寫(xiě)后序遍歷序列。根據(jù)預(yù)排序，樹(shù)的根節(jié)點(diǎn)是a；根據(jù)中間順序和根節(jié)點(diǎn)，B、D、C、E在根節(jié)點(diǎn)的左子樹(shù)上，H、F在根節(jié)點(diǎn)的右子樹(shù)上；通過(guò)對(duì)每個(gè)子樹(shù)的逐步分析，樹(shù)是a/b f/C H/De首先了解的概念：前序遍歷：訪(fǎng)問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前。中間順序遍歷：訪(fǎng)問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)時(shí)。后序遍歷：訪(fǎng)問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后。例：遍歷dbcefgha后，為了遍歷edcbahfg，先查找前序遍歷（聯(lián)機(jī)示例）解決方案：遍歷dbcefgha后，先看a是總根節(jié)點(diǎn)，然后按順序遍歷edcbahfg找到a的位置，然后edcb在a的左分支，HFG在a的右分支。重復(fù)前兩步，查找從最后一個(gè)位置對(duì)應(yīng)點(diǎn)進(jìn)行遍歷后，依次找到左右分支進(jìn)行遍歷，最后得到aecdbhgf，然后自己驗(yàn)證