平衡二叉树最大深度log2n,平衡二叉树最大深度公式

二叉树的层数和深度log2n

在二叉树的第i层上最多有2^(i-1)个结点. 深度为i的二叉树最多有2^k-1个结点(k=1)

满意请采纳

具有n个结点的平衡二叉树的深度一定不小于log2n

深度为k的二叉树的节点总数最多为1+2+4+..+2^(k-1)=2^k-1

则设n个节点的二叉树深度为m,2^m-1=n

m=log2(n+1)log(2n),由于m是整数

m=[log2n]+1,

n个节点的平衡二叉树,最大高度和最小高度是多少

高度为log2(n+1)，seethepic

数据结构课本上有最大高度。

最小高度就是完全二叉树了。

设N是深度为h的平衡二叉树的最少结点数，对于 h = 1，有 N = F(h + 2) - 1 成立，其中的F(n)为Fibonacci 数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

于是最大高度H为F(H + 2) - 1 = n F(H + 3) - 1

扩展资料：

若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点。

当i1时，该节点的双亲节点的编号为i/2。

若2i≤n，则有编号为2的左叶子，否则没有左叶子。

若2+1≤n，则有编号为2i+1的右叶子，否则没有右叶子。

参考资料来源：百度百科-二叉树

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

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