早教吧 育儿知识 作业答案 考试题库 百科 知识分享

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

题目详情
有n个结点的二叉树,已知叶子结点个数为n0,回答下列问题:
(1)写出求度为1的结点的个数n1的计算公式;
(2)若此树是深度为k的完全二叉树,写出n为最小的公式;
(3)若二叉树中仅有度为0和度为2的结点,写出求该二叉树结点个数n的公式;
▼优质解答
答案和解析
(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.