Question

12个结点的平衡二叉树的最大深度为

书上写含n个结点的AVL的最大深度为log2n，那这样算出来最大深度为4？
可是网上也很多说法说是5？

Answer 1

假设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。

Answer 2

二叉树的深度为12。
因为叶子节点为1个，按二叉树理论得出（任意一棵二叉树中度为0的节点总是比度为2的节点多一个），故得出此二叉树度为2的节点为0个。
12（总节点）-1（度为0）- 0（度为2）=11（度为1）。
故证明此二叉树每层只有1个节点，总共12层。

Answer 3

引用走在乡间的天蝎的回答：
二叉树的深度为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

Answer 4

那个是O(log2n)是数量级，不能在公式里算。
你层层嵌套算就好了。
N5=N4+N3+1
依次类推。
N1=1 N2=2 N3=4 N4=7

Answer 5

这个公式的根节点不算高度，所以结果要加，1