假设Nh表示深度为h的平衡二叉树中含有的最少的结点数目。那么,N0=0,N1=1,N2=2,并且Nh=Nh-1+Nh-2+1。
根据公式先计算出N3
N3=2+1+1
计算出N4
N4=4+2+1
最后出结果
N5=7+4+1
这时候N5就等于12
N后面跟的数字就是深度
扩展资料:
高为h的BT, 其结点的数目在2^(h+1)-1和1/2(3^(h+1)1)之间, 叶的数目在2^h和3^h之间。
证明:BT退化为每个结点 (非叶) 只有两棵子树时, 结点的数目最少, 叶子也最少。设层号为i则各层结点数为2^(i-1)个, 那么高为h的BT最大层号是j时, 有h=j-1。
整个树的结点数为s=2^0+2^1+2^2+…+2^h, 故s=2^(h+1)-1。其叶子的个数是2^h。同理, 当BT每个非叶结点都有三棵子数时, 结点数目最多。此时结点数为:
s=3^0+3^1+3^2+⋯+3^h‚s=1/2(3^(h+1)−1),其叶子的个数是3^h。
二叉树的深度为12。
因为叶子节点为1个,按二叉树理论得出(任意一棵二叉树中度为0的节点总是比度为2的节点多一个),故得出此二叉树度为2的节点为0个。
12(总节点)-1(度为0)- 0(度为2)=11(度为1)。
故证明此二叉树每层只有1个节点,总共12层。
上面答案是错的,明显
明显 用公式Nh=N(h-1)+N(h-2)+1
你算一下 当h=5时 正好是12
那个是O(log2n)是数量级,不能在公式里算。
你层层嵌套算就好了。
N5=N4+N3+1
依次类推。
N1=1 N2=2 N3=4 N4=7
这个公式的根节点不算高度,所以结果要加,1