2. 计算机
  3. 一棵二叉树含有ABCDEFGH共8个结点，对其进行先序、中序、后序遍历的结果分别如下：#BC#E#GH、C#DA#GHF、#DB# #FEA，“#”表示不清楚是什么结点。那么该二叉树度为1的结点共有(7)个。

一棵二叉树含有ABCDEFGH共8个结点，对其进行先序、中序、后序遍历的结果分别如下：#BC#E#GH、C#DA#GHF、#DB# #FEA，“#”表示不清楚是什么结点。那么该二叉树度为1的结点共有(7)个。

admin2013-05-11  22
问题 一棵二叉树含有ABCDEFGH共8个结点，对其进行先序、中序、后序遍历的结果分别如下：#BC#E#GH、C#DA#GHF、#DB# #FEA，“#”表示不清楚是什么结点。那么该二叉树度为1的结点共有(7)个。
选项 A、5
B、4
C、3
D、2
答案C
解析 后序遍历的最后一个结点A便是根结点，于是先序遍历便进一步明确为ABC#E #GH。在中序遍历中，根结点A将左右子树的结点刚好隔开，左子树结点为C并D，共3个结点，那么先序遍历中根结点A之后紧跟的3个结点BC#也是左子树结点，经对比我们显然可以推知左子树有结点B、C、D，于是先序遍历为ABCDE#GH，而中序遍历为 CBDA#GHF，此时，分别只剩下结点F、E，于是先序遍历为ABCDEFGH，而中序遍历为CBDAEGHF。在后序遍历中，显然前3个结点并DB是左子树结点(因为从中序遍历中可知根结点A之前有3个结点，便断定左子树共有三个结点)，接下来4个紧挨的结点# #FE是右子树结点，因此后序遍历便进一步明确为CDB# #FEA。右子树先序、后序遍历分别为EFGH、EGHF，又由二叉树的前序遍历可以确定该二叉树的根结点(序列的第一个结点)，在中序序列中该根结点将中序序列分为两部分，左边为其左子树的结点，右边为其右子树的结点，递归地操作下去便可以推知右子树的形状如图13-41所示。右子树的后序遍历为HGFE，于是整个树的后序遍历为CDBHGFEA。按同样的方法，我们可以得出整个二叉树的形状如图13-42所示。显然，度为1的结点为E、F、G共3个。
转载请注明原文地址:https://jikaoti.com/ti/KTf7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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