题目
假设高度为h的二叉树上只有度为0 和度为2的结点,则此类二叉树中所包含的结点数至少为_____。A. 2hB. 2h-1C. 2h+1D. h+1
假设高度为h的二叉树上只有度为0 和度为2的结点,则此类二叉树中所包含的结点数至少为_____。
A. 2h
B. 2h-1
C. 2h+1
D. h+1
题目解答
答案
B. 2h-1
解析
步骤 1:定义二叉树的性质
在二叉树中,度为0的结点(叶子结点)的数量比度为2的结点的数量多1。这是因为每个度为2的结点都有两个子结点,而度为0的结点没有子结点。因此,度为2的结点的子结点数量等于度为0的结点的数量减1。
步骤 2:计算度为2的结点数量
设度为2的结点数量为n,则度为0的结点数量为n+1。因为高度为h的二叉树的深度为h,所以度为2的结点数量n至少为h-1(因为根结点是度为2的结点,而高度为h的二叉树有h-1层度为2的结点)。
步骤 3:计算结点总数
结点总数为度为2的结点数量加上度为0的结点数量,即n+(n+1)。将n=h-1代入,得到结点总数为(h-1)+(h-1+1)=2h-1。
在二叉树中,度为0的结点(叶子结点)的数量比度为2的结点的数量多1。这是因为每个度为2的结点都有两个子结点,而度为0的结点没有子结点。因此,度为2的结点的子结点数量等于度为0的结点的数量减1。
步骤 2:计算度为2的结点数量
设度为2的结点数量为n,则度为0的结点数量为n+1。因为高度为h的二叉树的深度为h,所以度为2的结点数量n至少为h-1(因为根结点是度为2的结点,而高度为h的二叉树有h-1层度为2的结点)。
步骤 3:计算结点总数
结点总数为度为2的结点数量加上度为0的结点数量,即n+(n+1)。将n=h-1代入,得到结点总数为(h-1)+(h-1+1)=2h-1。