二叉樹遍歷例題

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

以下面的例題為例進行講解：

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

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

中序：dgbaechf --> dgb a echf

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

中序：dgb --> dg b

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

中序：dg --> d g

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

中序：echf --> e c hf

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

中序：hf --> h f

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

a

b c

d e f

g h后序遍歷序列：gdbehfca

前序遍歷是什么

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

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