Question

知道二叉树先序，中序，后序其中的两个顺序列，如何画出二叉树

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励30（财富值+成长值）

Answer 1

（1）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。
（2）由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。
设先序序列为：a1，a2，……，an ， 中序序列为：ap1，…，api， a1， …，apn 。则a1为根结点；ap1，…，api为左子树的中序序列，a2，…，ai-1为左子树的先序序列。
同样，也可确定右子树的中序和先序序列。 按照上面方法对左子树和右子树可确定各自的根。继续下去即构造出二叉树。
（3）由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。
设后序序列为：a2，……，an ， a1； 中序序列为：ap1，…，api， a1， …，apn 。则 a1为根结点；ap1，…，api为左子树的中序序列，a2，…，ai-1为左子树的后序序列。
同样，也可确定右子树的中序和后序序列。按照上面方法对左子树和右子树可确定各自的根。继续下去即构造出二叉树。