數(shù)據(jù)結(jié)構(gòu)中序和后序怎么畫二叉樹？例如中間順序：dgbaechf//左根右根后順序：gdbehfca//左根和右根（1）確定根從后順序獲取中間順序：（DGB）a（echf）后順序：（GDB）（ehfc）

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

例如

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

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

（1）確定根

從后順序獲取

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

（2）確定左節(jié)點(diǎn)

從頂部已知，左節(jié)點(diǎn)沒有節(jié)點(diǎn)

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

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

確定整棵樹為

---a-------------]---B-------------C-------------D-------------E-------------f-------------]---g-------------H----------

一棵二叉樹可以由兩次遍歷的順序唯一確定。例如，給定一個(gè)二叉樹，前序序列是abdecfg，中序序列是dbeafcg。二叉樹的根可以由前序序列確定為a，因?yàn)榍靶虮闅v順序是從根到左子樹再到右子樹。從中序序列可以看出DBE在a的左子樹中，F(xiàn)CG在a的右子樹中，因?yàn)锽在前序序列中跟隨a，所以B必須是a的左子樹的根。在前序序列中，a的左子樹是DBE。前序序列的遍歷順序?yàn)椋鹤笞訕?、父子樹和右子樹。我們可以看到D是B的左子樹，E是B的右子樹。我們也可以分析根a的右子樹。前序序列中的ABDE已經(jīng)遍歷了根和左子樹，所以剩余的CFG就是右子樹遍歷的序列?？梢钥闯?，C是右子樹的根，f是C的左子樹，G是C的右子樹，因此，二叉樹的序列遍歷順序應(yīng)該是ABCDEFG。