2. 计算机
  3. 已知一棵二叉树的前序遍历结果为ABDEGCFHI，它的中序遍历结果为DBGEACHFI，则这棵二叉树的右子树的根为【 】。

已知一棵二叉树的前序遍历结果为ABDEGCFHI，它的中序遍历结果为DBGEACHFI，则这棵二叉树的右子树的根为【 】。

admin2010-05-13  37
问题 已知一棵二叉树的前序遍历结果为ABDEGCFHI，它的中序遍历结果为DBGEACHFI，则这棵二叉树的右子树的根为【  】。
选项
答案C
解析 已知某二叉树的前序遍历结果和中序遍历结果可以惟一确定一棵二叉树。其确定过程是：在二叉树的前序遍历序列中确定该树的根结点，随后由根结点在中序遍历结果中的位置区分出根结点左子树和右子树中的结点；此后采用同样的方法分别确定二叉树左右子树的根结点及其左子树和右子树所含的结点，直到将二叉树中所有结点的位置确定下来。以本题为例，因位于二叉树前序遍历结果的第一个结点是二叉树的根结点，故本题中结点A是二叉树的根结点。在中序遍历结果中，先于根结点被访问的结点是根结点左子树中的结点，在根结点之后被访问的结点是根结点右子树中的结点。因此， DBGE是结点A左子树中的结点，CHFI是结点A右子树中的结点。在前序遍历结果中，结点A左子树中各结点的遍历顺序为BDEG，所以A的左孩子结点是B。由中序遍历结果可知，结点B的左子树中含有结点D，其右子树中含有结点G和E。又由于在前序遍历序列中结点E在G之前，中序遍历序列中G在E之前，所以G是E的左孩子结点。至此，根结点左子树中各结点的位置均已确定下来，此后采用同样的方法确定其右子树中各结点的位置。最终所求的二叉树如左图所示。
转载请注明原文地址:https://kaotiyun.com/show/aZSZ777K
本试题收录于： 三级数据库技术题库NCRE全国计算机三级分类
0

三级数据库技术

NCRE全国计算机三级

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