已知某二叉树的先序遍历序列是ABDCE,中序遍历序列是BDAEC,则该二叉树为()。
A.A
B.B
C.C
D.D
参考答案:C
解析:
本题考查数据结构的基础知识。
解法1:从考查的知识点入手寻找答案
二叉树(Binarv Tree)是一种树型结构,它的特点是每个结点至多只有两棵子树,并且二叉树的子树有左右之分,其次序不能任意颠倒。遍历二叉树一般有三种情况,分别是先序遍历二叉树、中序遍历二叉树和后序遍历二叉树。
(1)先序遍历二叉树的过程为:若二叉树为空,则空操作。否则
·访问根结点:
·先序遍历左子树;
·先序遍历右子树。
(2)中序遍历二叉树的过程为:若二叉树为空,则空操作。否则
·中序遍历左子树;
·访问根结点;
·中序遍历右子树。
(3)后序遍历二叉树的过程为:若二叉树为空,则空操作。否则
·后序遍历左子树;
·后序遍历右子树;
·访问根结点。
因此,可以根据先序遍历序列和中序遍历序列恢复二叉树的结构。根据先序序列确定根结点为A;根据中序遍历序列划分出左子树BD,右子树EC。中序遍历和先序遍历中B都在D前,所以B是左子树的根结点,D是B的右孩子。中序遍历中E在C前,所以有两种情况:第一种E是右子树的根结点,C是E的右孩子;第二种C是右子树的根结点,E是C的左孩子。在先序遍历中C在E前,由此第二种情况成立,得到二叉树的结构如图1.11所示。
[*]
解法2:选项验证法
把选项代入进行验证,若存在与二叉树遍历过程不符处,即排除该项,直到找到答案。选项A和B中,B是左子树的根结点,D是B的左孩子,与中序遍历过程“左一根一右”不符,这两个选项可排除。选项D中,C是右子树的根结点,E是C的右孩子,与中序遍历过程“左一根一右”不符,这个选项可排除。选项C符合要求。