一棵二叉树含有ABCDEFGH共8个结点,对其进行先序、中序、后序遍历的结果分别如下:#BC#E#GH、C#DA#GHF

Question

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

A．5

B．4

C．3

D．2

Answer 1

正确答案：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个。