有n个结点的二叉树,已知叶子结点个数为n0,回答下列问题：(1)写出求度为1的结点的个数n1的计算公式；(2)若此树是深度为k的完全二叉树,写出n为最小的公式；(3)若二叉树中仅有度为0和度为2的

Question

有n个结点的二叉树,已知叶子结点个数为n0,回答下列问题：
(1)写出求度为1的结点的个数n1的计算公式；
(2)若此树是深度为k的完全二叉树,写出n为最小的公式；
(3)若二叉树中仅有度为0和度为2的结点,写出求该二叉树结点个数n的公式；

Answer 1

(1)n1=n-2n0+1
(2)n=n0+2^(k-1) -1
(3)n=2n0-1
二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T,如果其终端结点数(即叶子结点数)为n0,度为2的结点数为n2,则n0 = n2 + 1.