四川874专业考研-二叉树遍历序列的应用

同学们在做树和二叉树这章题的过程中，应该会遇到过以下类型的题：

设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC，要求：画出这棵二叉树。

这种类型的题通常会给我们二叉树的两个遍历序列，一般是先序遍历序列和中序遍历序列，或者是后序遍历序列和中序遍历序列。可能很多同学遇到这种题会比较懵，直接选择经过各种试探来构造这棵二叉树。然后，做这种题是有规律可循的，今天我们就来讨论这类题的解题思路。

首先，我们知道，先序遍历序列是根左右的形式即DLR形式，对于上面的例题而言，先序序列中的第一个结点A就是根结点;中序遍历序列是左根右的形式即LDR形式，所以当我们由先序序列确定出A是根结点之后，A把中序序列分成两个子序列，A左面的序列就是根结点A左子树上的结点集合，A右面的序列就是根结点A右子树上的结点集合，对于左右两子树的集合，我们又可以先序序列中先出现的结点确定哪个结点是子树的根，比如左子树结点集合为B，F，D组成，而在先序序列中B先于D和F出现，说明B是根A的左子树的根，相应的，C是根A的右子树的根，以此类推，得到由先序序列：ABDFCEGH以及中序序列：BFDAGEHC确定的唯一一棵二叉树，如下图所示。简言之，由先序序列确定哪些结点是根或子树的根，由中序序列确定哪些结点是左子树结点集合以及右子树结点集合。同理，由后序序列和中序序列也可唯一确定一棵二叉树。

这个世界上根本没有正确的选择，我们只不过是要努力奋斗，使当初的选择变得正确!