二叉樹的性質

二叉樹具有以下重要性質
性質 二叉樹第i層上的結點數目最多為i(i≥)
證明用數學歸納法證明
　　　歸納基礎i=時有ⁱ==因為第層上只有一個根結點所以命題成立
　　　歸納假設假設對所有的j(≤j<i)命題成立即第j層上至多有^j個結點證明j=i時命題亦成立
　　　歸納步驟根據歸納假設第i層上至多有ⁱ個結點由於二叉樹的每個結點至多有兩個孩子故第i層上的結點數至多是第i層上的最大結點數的倍即j=i時該層上至多有×ⁱ=ⁱ個結點故命題成立

性質 深度為k的二叉樹至多有^k個結點(k≥)
證明在具有相同深度的二叉樹中僅當每一層都含有最大結點數時其樹中結點數最多因此利用性質可得深度為k的二叉樹的結點數至多為
                ++…+^k=^k
　　故命題正確

性質 在任意棵二叉樹中若終端結點的個數為n度為的結點數為n則no=n+
證明因為二叉樹中所有結點的度數均不大於所以結點總數(記為n)應等於度結點數度結點(記為n)和度結點數之和
                     n=n_o+n+n (式子)
　　　另一方面度結點有一個孩子度結點有兩個孩子故二叉樹中孩子結點總數是
                      n_l+n
　　樹中只有根結點不是任何結點的孩子故二叉樹中的結點總數又可表示為
                      n=n+n+ (式子)
　　由式子和式子得到
                      n_o=n+

滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形
滿二叉樹(FullBinaryTree)
　　一棵深度為k且有^k個結點的二又樹稱為滿二叉樹
　　滿二叉樹的特點
　　（） 每一層上的結點數都達到最大值即對給定的高度它是具有最多結點數的二叉樹
　　（） 滿二叉樹中不存在度數為的結點每個分支結點均有兩棵高度相同的子樹且樹葉都在最下一層上
　　【例】圖(a)是一個深度為的滿二叉樹

完全二叉樹(Complete BinaryTree)
　　若一棵二叉樹至多只有最下面的兩層上結點的度數可以小於並且最下一層上的結點都集中在該層最左邊的若干位置上則此二叉樹稱為完全二叉樹
　特點
　（） 滿二叉樹是完全二叉樹完全二叉樹不一定是滿二叉樹
　（） 在滿二叉樹的最下一層上從最右邊開始連續刪去若干結點後得到的二叉樹仍然是一棵完全二叉樹
　（） 在完全二叉樹中若某個結點沒有左孩子則它一定沒有右孩子即該結點必是葉結點
【例】如圖(c)中結點F沒有左孩子而有右孩子L故它不是一棵完全二叉樹
【例】圖(b)是一棵完全二叉樹
 
性質  具有n個結點的完全二叉樹的深度為
                          
證明設所求完全二叉樹的深度為k由完全二叉樹定義可得
　　深度為k得完全二叉樹的前k層是深度為k的滿二叉樹一共有^k個結點
由於完全二叉樹深度為k故第k層上還有若干個結點因此該完全二叉樹的結點個數
                  n>^k
　　另一方面由性質可得
                  n≤^k
       即^kl<n≤^k
　　由此可推出^k≤n<^k取對數後有
                  k≤lgn<k
　　又因k和k是相鄰的兩個整數故有
                                   
　　由此即得
                 
注意
　　的證明【參見參考書目】

From:http://tw.wingwit.com/Article/program/sjjg/201311/23284.html