．（）
（）設二叉樹的前序遍歷序列為PP…Pm中序遍歷序列為SS…Sm因為前序遍歷是根左右中序遍歷是左根右則前序遍歷序列中第一個結點是根結點（P）到中序序列中查詢到Si=P根據中序遍歷時根結點將中序序列分成兩部分的原則有
若i=即S=P則這時的二叉樹沒有左子樹; 否則SS…Si是左子樹的中序遍歷序列用該序列和前序序列PP…Pi去構造該二叉樹的左子樹
若i=m即Sm=P則這時的二叉樹沒有右子樹; 否則Si+Si+…Sm是右子樹的中序遍歷序列用該序列和前序序列中Pi+Pi+…Pm去構造該二叉樹的右子樹算法描述請參見下面算法設計第題
（）若前序序列是abcd並非由這四個字母的任意組合（!=）都能構造出二叉樹因為以abcd為輸入序列通過棧只能得到/(n+)*n!/(n!*n!)= 種即以abcd為前序序列的二叉樹的數目是任取以abcd作為中序遍歷序列並不全能與前序的abcd序列構成二叉樹例如若取中序列dcab就不能
該棵二叉樹的形態及中序序列略
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22656.html
