问题
问答题
对任何一棵二叉树,如果终端结点数为n0,度为2的结点数为n2,则一定有n0=n2+1。
答案
参考答案:[证明] 假设二叉树中度为1的结点个数为n。,结点总数为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。