數(shù)據(jù)結(jié)構(gòu)中已知前序序列和中序序列，怎么得出后序序列？首先要明確前序、中序、后序的遍歷順序：前序：父節(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ù)

數(shù)據(jù)結(jié)構(gòu)中已知前序序列和中序序列，怎么得出后序序列？

首先要明確前序、中序、后序的遍歷順序：前序：父節(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ò)中間序遍歷，將整個(gè)二叉樹(shù)按根節(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ò)逐步分析子樹(shù)，樹(shù)是a/╲B F/╲C h/╲D E，后跟decbhfa

例如

中間順序：dgbaechf//左根右根

最后順序：gdbehfca//左根和右根

（1）determine root

get

中間順序：（DGB）a（echf）最后順序：（GDB）（ehfc）a

（2）determine left node

從上面知道，左節(jié)點(diǎn)沒(méi)有節(jié)點(diǎn)

（3）確定右節(jié)點(diǎn)

中間順序[（E）C（HF）]最后順序：[（E）（HF）C]

確定整個(gè)樹(shù)為

數(shù)據(jù)結(jié)構(gòu)中序和后序怎么畫(huà)二叉樹(shù)？

找到根節(jié)點(diǎn)（通過(guò)post順序），然后把中間順序序列分成兩段，左子樹(shù)和右子樹(shù)，然后遞歸地，在分割時(shí)，可以用中間順序的左子樹(shù)和右子樹(shù)的節(jié)點(diǎn)數(shù)來(lái)確定后順序序列Dbeca

1中每段的節(jié)點(diǎn)數(shù)。最后一個(gè)節(jié)點(diǎn)必須是根節(jié)點(diǎn)，在本例中是a

2。中間順序?qū)?yīng)的根是a，所以a是根，BD是左子樹(shù)，CE是右子樹(shù)

3。左子樹(shù)中有兩個(gè)節(jié)點(diǎn)，右子樹(shù)中有兩個(gè)節(jié)點(diǎn)，因?yàn)楹笠豁樞虮闅v是先左后右，所以后一順序被分成兩段，左dB，右EC

4。因此，左子樹(shù)的根被確定為B，右子樹(shù)的根被確定為C

5，順序是左子樹(shù)部分BD（B是根），其右子樹(shù)是D，左子樹(shù)部分根是C，右子樹(shù)部分根是e

是前序ABCDE，首先恢復(fù)二叉樹(shù)，然后遍歷后序序列得到后序序列。恢復(fù)過(guò)程如下：首先，前序序列的第一根是根。在得到中間順序后，中間順序可分為三部分：左子樹(shù)的中間順序、右子樹(shù)的根和中間順序。然后，將左子樹(shù)的中階和右子樹(shù)的中階分別返回到樹(shù)的前階序列中，子樹(shù)的根仍然在第一位，然后返回到子樹(shù)的中階進(jìn)行切割，直到所有子樹(shù)只有一個(gè)節(jié)點(diǎn)