在一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则有n0__________。

admin2014-08-29 75

问题在一棵二叉树中，度为零的结点个数为n₀，度为2的结点个数为n₂，则有n₀__________。

选项

答案n2+1

解析假设二叉树中度为1的结点个数为n1，结点总数为n。因为二叉树中任何结点的度最大不超过2，因此有：n=n0+n1+n2(1)从另一个角度看，我们来研究二叉树的分支数。对所有结点来说，除了根结点，任何其余结点都有一个分支进入(指向)。不妨设B(Branch)为二叉树的分支数，则有：B=n一1(分支数比结点数少1)(2)而分支是由度为1的结点和度为2的结点贡献的：每个度为1的结点贡献1个分支，每个度为2的结点贡献2个分支。则有：B=n1×1+n2×2=n1+2n2(3)由(2)、(3)得n=n1+2n2+1(4)由(1)、(4)得n0=n2+1由此得出结论：二叉树叶子结点个数总是比度为2的结点个数多1。

转载请注明原文地址:https://kaotiyun.com/show/SyvR777K

本试题收录于：计算机科学与技术题库普高专升本分类

计算机科学与技术

普高专升本

相关试题推荐

随机试题

最新回复(0)

在一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则有n0__________。

计算机科学与技术

普高专升本

特发性血小板减少性紫厕的特征不包括()。

抗休克过程中微循环好转的标志是()。．

按系统与环境的关系，系统分为()。

执行胆囊造影饮食时，正确的护理方法是()。

根据均匀性假设，可认为构件横截面上各点处的应力都相同。()

胚胎时肾小管与集合管不交通，致使肾小管分泌物排出困难所引致的肾的畸形和异常是()

在一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则有n0__________。

找出一个二维数组中的鞍点，即该位置上的元素在该行上最大，在该列上最小。也可能没有鞍点。程序中有几处错误代码，请指出并改正之。不得增加行或删除行，也不得更改程序结构。(1)main(){(2)inti，j，k，flag1，flag2，a[N][

对于有N个结点的二叉树，其高度为log2n。()

髋关节前后位摄影时，应使足尖

意大利的国教是基督教新教。()

窗体上有一个菜单编辑器设计的菜单。运行程序，并在窗体上单击鼠标右键，则弹出一个快捷菜单，如图所示。

用GHz来衡量计算机的性能，它指的是计算机的

Wehadgonethere______toplanttreesinthegarden.

Comparisonsweredrawnbetweenthedevelopmentoftelevisioninthe20thcenturyandthediffusionofprintinginthe15thand1