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

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

admin2014-08-29  58
问题 在一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2，则有n0__________。
选项
答案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

计算机科学与技术

普高专升本

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