当前位置:首页>维修大全>综合>

完全二叉树结点深度计算公式(二叉树的结点数计算公式图解)

完全二叉树结点深度计算公式(二叉树的结点数计算公式图解)

更新时间:2024-05-04 07:05:04

完全二叉树结点深度计算公式

计算二叉树的深度 :

满二叉树的深度为k=log2(n+1)

在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。

计算完全二叉树深度公式-推导证明:

假设两种极端情况

<1>该树为满二叉树时,结点n1=2^k-1

此时k=log2(n1+1)

<2>当该树为满二叉树附加一个结点时,n2=2^(k-1),此时k=log2n2 +1,

并且log2(n1+1)=log2n2 +1

对任意结点n的完全二叉树,n2<=n<=n1

2^(k-1)<=n<=2^k -1

log2(n+1)<=k<=log2n +1

则k向下取整log2n +1

更多栏目