具有n个结点的完全二叉树的深度为log2n+1 证明过程是怎样的

2024-12-01 01:31:51
推荐回答(1个)
回答1:

假设完全二叉树深度为k,则第k层至多有2^(k -1)个结点。最少是2^(k -2) +1(这里k>1)
那么深度为k的完全二叉树 结点总数最多有 1 + 2 + 4 + ... + 2^(k -1) = 2^k - 1
深度为k的完全二叉树结点总数关系式是: 2^(k-1)