填空题
某二叉树中度为2的结点有18个,则该二又树中有
1
个叶子结点。
1、
【正确答案】
1、19
【答案解析】
[解析] 根据公式进行推导,假设n
0
,是度为0的结点总数(即叶子结点数),n
1
是度为1的结点总数,n
2
是度为2的结点总数,由二又树的性质可知:n
0
=n
2
+1,则n=n
0
+n
1
+n
2
(其中n为完全二叉树的结点总数),由上述公式把n
2
消去得n=2n
0
+n
1
-1,由于完全二叉树中度为1的结点数只有0或1两种可能,由此得到n
0
=(n+1)/2或n
0
=n/2,合并成一个公式n
0
=(n+1)/2。
提交答案
关闭