數據結構考研分類復習真題 第六章 答案 (四)[12]

　　．證明請參見第題和第題

　　由前序序列ABDGECFH和中序序列DGBEAFHC構造的二叉樹如圖

　　．參見第題

　　．先序遍歷二叉樹的順序是根左子樹右子樹中序遍歷左子樹根右子樹後序遍歷順序是左子樹右子樹―根＂根據以上原則本題解答如下

　　若先序序列與後序序列相同則或為空樹或為只有根結點的二叉樹

　　若中序序列與後序序列相同則或為空樹或為任一結點至多只有左子樹的二叉樹

　　若先序序列與中序序列相同則或為空樹或為任一結點至多只有右子樹的二叉樹

　　若中序序列與層次遍歷序列相同則或為空樹或為任一結點至多只有右子樹的二叉樹

　　由中序序列DBEAFIHCG和後序序列DEBHIFGCA確定的二叉樹略

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22653.html