问题 单项选择题

已知某二叉树的先序遍历序列是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符合要求。

填空题
单项选择题