A-A+

对于任何一棵非空的二叉树假设叶子结点的个数为n0 而次数为2的结点个数为n2 请给出n0和

2022-08-12 16:01:12 问答库阅读 196 次

问题详情

对于任何一棵非空的二叉树，假设叶子结点的个数为n0，而次数为2的结点个数为n2，请给出n0和n2之间所满足的关系式n0=f(n2)。要求给出推导过程。

请帮忙给出正确答案和分析，谢谢！

参考答案

正确答案：设度为1和2及叶子结点数分别为n₀、n₁和n₂则二叉树结点数n为n=n₀+n₁+n₂ (1)再看二叉树的分支数除根结点外其余结点都有一个分支进入设B为分支总数则n=B+1。度为1和2的结点各有1个和2个分支度为0的结点没有分支故n=n₁+2n₂+1 (2)由式(1)和式(2)得n₀=n₂+1。
设度为1和2及叶子结点数分别为n0、n1和n2,则二叉树结点数n为n=n0+n1+n2(1)再看二叉树的分支数,除根结点外,其余结点都有一个分支进入,设B为分支总数,则n=B+1。度为1和2的结点各有1个和2个分支,度为0的结点没有分支,故n=n1+2n2+1(2)由式(1)和式(2),得n0=n2+1。