假設(shè)某二叉樹的先序遍歷序列是abdgcefh，中序遍歷序列是dgbaechf，畫出二叉樹，并給出其后序遍歷序列。分析過程：

以下面的例題為例進(jìn)行講解：

已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別是abdgcefh、dgbaechf，求二叉樹及后序遍歷序列。

分析：先序遍歷序列的第一個(gè)字符為根結(jié)點(diǎn)。對(duì)于中序遍歷，根結(jié)點(diǎn)在中序遍歷序列的中間，左邊部分是根結(jié)點(diǎn)的左子樹的中序遍歷序列，右邊部分是根結(jié)點(diǎn)的右子樹的中序遍歷序列。先序：abdgcefh --> a bdg cefh

中序：dgbaechf --> dgb a echf

得出結(jié)論：a是樹根，a有左子樹和右子樹，左子樹有bdg結(jié)點(diǎn)，右子樹有cefh結(jié)點(diǎn)。先序：bdg --> b dg

中序：dgb --> dg b

得出結(jié)論：b是左子樹的根結(jié)點(diǎn)，b無右子樹，有左子樹。先序：dg --> d g

中序：dg --> d g

得出結(jié)論：d是b的左子樹的根結(jié)點(diǎn)，d無左子樹，有右子樹。先序：cefh --> c e fh

中序：echf --> e c hf

得出結(jié)論：c是右子樹的根結(jié)點(diǎn)，c有左子樹(只有e結(jié)點(diǎn))，有右子樹(有fh結(jié)點(diǎn))。先序：fh --> f h

中序：hf --> h f

得出結(jié)論：f是c的左子樹的根結(jié)點(diǎn)，f有左子樹(只有h結(jié)點(diǎn))，無右子樹。還原二叉樹為：

a

b c

d e f

g h后序遍歷序列：gdbehfca

前序遍歷是什么

這個(gè)是二叉樹里面的一種遍歷情況，前序遍歷也叫做先根遍歷，可記做根左右。

前序遍歷首先訪問根結(jié)點(diǎn)然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。