高為h的滿二叉樹的結(jié)點數(shù)為：$2^h?1$
各層結(jié)點數(shù)為$2^0,2^1,...,2^{h?1}$
根據(jù)等比序列求和公式，可得到總結(jié)點數(shù)：$s=1(1?2^h)/(1?2)=2^h?1$

高為h的完全二叉樹的結(jié)點數(shù)范圍為：$[2^{h?1},2^h?1]$
結(jié)點最少情況為：h-1層滿二叉樹加1個結(jié)點。
結(jié)點最多情況為：h層滿二叉樹。

結(jié)點數(shù)為n的滿二叉樹層數(shù)為：$lo{g}_2(n+1)$
證明：
$2^h?1=n$
$2^h=n+1$
$h=lo{g}_2(n+1)$

結(jié)點數(shù)為n的完全二叉樹層數(shù)為：$?lo{g}_{2}n?+1$
證明：
設(shè)該二叉樹有h層，第h層有m個結(jié)點
要證明：$h=?lo{g}_{2}n?+1$
前h-1層是滿二叉樹，共$n?m$個結(jié)點，
即$h?1=lo{g}_2(n?m+1)$
$h=lo{g}_2(n?m+1)+1$
因為：$m\ge 1$，所以：$m?1\ge 0$
因此：$lo{g}_{2}n\ge lo{g}_2(n?(m?1))$
所以：$lo{g}_{2}n+1\ge lo{g}_2(n?m+1)+1=h$
第h層的結(jié)點數(shù)最多為$2^{h?1}$個
如樹的結(jié)點有$n?m+2^{h?1}$個，這就是一個h層滿二叉樹
此時$h=lo{g}_2(n?m+2^{h?1}+1)$
已知$1\le m\le 2^{h?1}$
那么 $m?1\le 2^{h?1}?1$
那么 $2^{h?1}?(m?1)\ge 1>0$
有$h=lo{g}_2(n+2^{h?1}?(m?1))>lo{g}_{2}n$
綜上，有$lo{g}_{2}n<h\le lo{g}_{2}n+1$
設(shè)$lo{g}_{2}n=?lo{g}_{2}n?+a$，
其中$0\le a<1$
即$?lo{g}_{2}n?+a<h\le ?lo{g}_{2}n?+a+1$
如果$a=0$
那么$?lo{g}_{2}n?<h\le ?lo{g}_{2}n?+1$
已知h是整數(shù)，有$h=?lo{g}_{2}n?+1$
如果$0<a<1$
那么$?lo{g}_{2}n?+a<?lo{g}_{2}n?+1\le h\le ?lo{g}_{2}n?+a+1$
此時有$h=?lo{g}_{2}n?+1$
命題得證

總結(jié)

以上是生活随笔為你收集整理的满二叉树及完全二叉树的相关性质证明的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。