校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 二叉树相关概念
题目

设高度为h(根的层次为1)的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为()

A.2h

B.2h - 1

C.2h + 1

D.h + 1

解答

正确答案是 B

对任何一颗二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。

由题意,该二叉树只有度为0和度为2的结点,则最下层之上每层至少有一个度为2的结点,即 n2 >= h-1,
总结点数 = n0+n2 = 2n2+1 >= 2(h-1)+1=2h-1 

C 0条回复 评论

帖子还没人回复快来抢沙发