()根據二叉樹度為 結點個數等於葉子結點個數減的性質故具有n個葉子結點且非葉子結點均有左左子樹的二叉樹的結點數是n
()證明當i=時（）==公式成立設當i=n時公式成立證明當i=n時公式仍成立
設某葉子結點的層號為t當將該結點變為內部結點從而再增加兩個葉子結點時這兩個葉子結點的層號都是t+對於公式的變化是減少了一個原來的葉子結點增加了兩個新葉子結點反映到公式中因為(t)=(t+)+(t+)所以結果不變這就證明當i=n時公式仍成立證畢．
．結點數的最大值h（滿二叉樹）最小值h（第一層根結點其余每層均兩個結點）
．（）k(u)++i () ë(v)/kû+ (參見第題推導)
．該二叉樹是按前序遍歷順序編號以根結點為編號前序遍歷的順序是根左右
．（）設n=則e=+*=（只有一個根結點時有兩個外部結點）公式成立
設有n個結點時公式成立即
En=In+n ()
現在要證明當有n+個結點時公式成立
增加一個內部結點設路徑長度為l則
In+=In+l ()
該內部結點其實是從一個外部結點變來的即這時相當於也增加了一個外部結點（原外部結點變成內部結點時增加兩個外部結點）則
En+=En+l+ ()
由（）和（）則（）推導為
En+=In+n+l+=In+l+n+l+
=In++(n+）
故命題成立
（）成功查找的平均比較次數s=I/n
不成功查找的平均比較次數u=（En）/（n+）=（I+n）/n+
由以上二式有s=（+/n）*u
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22649.html
