．給定二叉樹結點的前序序列和對稱序（中序）序列可以唯一確定該二叉樹因為前序序列的第一個元素是根結點該元素將二叉樹中序序列分成兩部分左邊（設l個元素）表示左子樹若左邊無元素則說明左子樹為空右邊（設r個元素）是右子樹若為空則右子樹為空根據前序遍歷中根?左子樹右子樹的順序則由從第二元素開始的l個結點序列和中序序列根左邊的l個結點序列構造左子樹由前序序列最後r個元素序列與中序序列根右邊的r個元素序列構造右子樹
由二叉樹的前序序列和後序序列不能唯一確定一棵二叉樹因無法確定左右子樹兩部分例如任何結點只有左子樹的二叉樹和任何結點只有右子樹的二叉樹其前序序列相同後序序列相同但卻是兩棵不同的二叉樹
．前序遍歷是根左右中序遍歷是左根右後序遍歷是左右根三種遍歷中只是訪問根結點的時機不同對左右子樹均是按左右順序來遍歷的因此所有葉子都按相同的相對位置出現
．在第題已經說明由二叉樹的前序序列和中序序列可以確定一棵二叉樹現在來證明由二叉樹的中序序列和後序序列也可以唯一確定一棵二叉樹
當n=時只有一個根結點由中序序列和後序序列可以確定這棵二叉樹
設當n=m時結論成立現證明當n=m時結論成立
設中序序列為SS…Sm後序序列是PP…Pm因後序序列最後一個元素Pm是根則在中序序列中可找到與Pm相等的結點（設二叉樹中各結點互不相同）Si(≤i≤m)因中序序列是由中序遍歷而得所以Si是根結點SS…Si是左子樹的中序序列而Si+Si+…Sm是右子樹的中序序列
若i=則S是根這時二叉樹的左子樹為空右子樹的結點數是m則{SS…Sm}和{PP…Pm}可以唯一確定右子樹從而也確定了二叉樹
若i=m則Sm是根這時二叉樹的右子樹為空左子樹的結點數是m則{SS…Sm}和{PP…Pm}唯一確定左子樹從而也確定了二叉樹
最後當<i<m時Si把中序序列分成{SS…Si}和{Si+Si+…Sm}由於後序遍歷是左子樹右子樹根結點所以{PP…Pi}和{PiPi+…Pm}是二叉樹的左子樹和右子樹的後序遍歷序列因而由{SS…Si}和{PP…Pi}
可唯一確定二叉樹的左子樹由{Si+Si+…Sm}和
{PiPi+…Pm}可唯一確定二叉樹的右子樹
由中序序列DBEAFGC和後序序列DEBGFCA構
造的二叉樹如圖
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22652.html
