5-5 根据遍历序列确定二叉树（1）

• 若二叉树种各结点的值均不相同，则二叉树结点的先序序列、中序序列和后序序列都是唯一的
• 由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树

【例题】已知二叉树的先序和中序序列，构造出相应的二叉树

先序:A B C D E F G H I J
中序:C D B F E A I H G J

分析：

1. 由先序序列确定根
2. 由中序序列确定左右子树

解：

1. 由先序知根为A，则由中序知左子树为CDBFE，右子树为IHGJ

   

2. 再分别在左、右子树的序列中找出根、左子树序列、右子树序列

   

3. 以此类推，直到得到二叉树

   

【例题】已知中序序列和后序序列求二叉树

请画出这棵二叉树

中序序列:B D C E A F H G
后序序列：D E C B H G F A

提示：后续遍历，根节点必在后许序列尾部

5-5 根据遍历序列确定二叉树（2）