2. 计算机
  3. 某二叉树的先序遍历(根、左、右)序列为EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG，则该二叉树根结点的左孩子结点和右孩子结点分别是___________。

某二叉树的先序遍历(根、左、右)序列为EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG，则该二叉树根结点的左孩子结点和右孩子结点分别是___________。

admin2019-05-11  45
问题 某二叉树的先序遍历(根、左、右)序列为EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG，则该二叉树根结点的左孩子结点和右孩子结点分别是___________。
选项 A、I、K
B、F、I
C、F、G
D、I、G
答案C
解析 本题考查数据结构基础知识。
    对于一个非空的二叉树，其先序遍历序列、中序遍历序列和后序遍历序列都是唯一确定的。先序遍历是首先访问根结点，其次是先序遍历左子树，最后再先序遍历右子树，因此先序序列的第一个元素是根结点。中序遍历是首先中序遍历左子树，然后访问根结点，最后中序遍历右子树，因此在已知根结点的情况下，可将左子树和右子树的结点区分开。
    本题中根据先序遍历序列可知E是根结点，在中序遍历序列中E之前是左子树的中序遍历序列，E之后是右子树的中序遍历序列。再到先序遍历序列中确定FHI为左子树的先序遍历序列、GJK为右子树的先序遍历序列。从而确定F为E的左孩子结点、G为E的右孩子结点。依此类推，可确定该二叉树如下图所示。
转载请注明原文地址:https://kaotiyun.com/show/EvVZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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