可用數(shù)學(xué)歸納法.
當(dāng)n=1=2^1-1時顯然.
假設(shè)當(dāng)n<=2^k-1時具有n個結(jié)點的完全二叉樹的深度為「log2n」+1,則
當(dāng)n=2^k（以及2^k+1,...,2^(k+1)-1）時,由歸納假設(shè)知前2^k-1個結(jié)點構(gòu)成深度為「log2n」+1的樹,再由完全二叉樹的定義知剩余的1（或2,...,2^k)個結(jié)點均填在第「log2n」+2層上（作為“葉子”）,故深度剛好增加了1.
故n<=2^(k+1)-1時命題成立.證畢.
（首先最好能先從直觀上理完全二叉樹中：
第1層有1個結(jié)點；
第2層有2個結(jié)點；
第3層有4個結(jié)點；……第k層有2^(k-1)個結(jié)點；（前k層共有(2^k)-1個結(jié)點,故前面深度剛好是「log2（2^k-1)」+1=k-1+1=k）
）