2. 计算机
  3. 某二叉树的先序遍历序列为ABCDEF，中序遍历序列为BADCFE，则该二叉树的高度(即层数)为___________。

某二叉树的先序遍历序列为ABCDEF，中序遍历序列为BADCFE，则该二叉树的高度(即层数)为___________。

admin2018-04-19  47
问题 某二叉树的先序遍历序列为ABCDEF，中序遍历序列为BADCFE，则该二叉树的高度(即层数)为___________。
选项 A、3
B、4
C、5
D、6
答案B
解析 本题考查数据结构基础知识。
    对于一个非空的二叉树，其先序遍历序列和中序遍历序列都是唯一确定的。先序遍历是首先访问根结点，其次先序遍历左子树，最后先序遍历右子树，因此先序序列中的第一个元素表示根结点。中序遍历是首先中序遍历左子树，然后访问根结点，最后中序遍历右子树，因此在已知根结点的情况下，可将左子树和右子树的结点区分开。
    本题中，根据先序遍历序列，可知树根结点是A，然后从中序序列得知左子树中只有一个结点(B)，依此类推，可推得该二叉树如下图所示，其高度为4。
转载请注明原文地址:https://www.kaotiyun.com/show/1iWZ777K
本试题收录于： 多媒体应用设计师上午基础知识考试题库软考中级分类
0

多媒体应用设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)