目錄
二叉樹的定義
二叉樹的性質
性質1 在二叉樹的第i層上至多有 2^(i-1)個結點，(i≥1)
性質2 深度為k的二叉樹至多有2^(k)-1個結點，(k≥1)
性質3 對任何一棵二叉樹T，若其終端結點數為n0，度數為2的結點數為n2，則n0=n2+1，
性質4 具有n個結點的完全二叉樹的深度為[log n]+1 或 log (n+1)，
二叉樹的定義
概述：所有結點的度都只為0、1、2的樹，就是二叉樹，
定義：二叉樹 (Binary Tree)是 n(n≥0)個結點的有限集合，它的每個結點至多只有兩棵子樹，它或者是空集，或者是由一個根結點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成，
二叉樹的五種基本形態：
二叉樹的性質
性質1 在二叉樹的第i層上至多有 2^(i-1)個結點，(i≥1)
證明：利用 ”數學歸納法" 進行證明，
(1) 當 i=1時，只有一個根結點，即 2^(i-1)=2^0=1，
(2) 歸納假設，第 i-1層上至多有 2^(i-2)個結點，因為二叉樹的每個結點的度至多為 2，所以在 "第 i層上的結點數目” 最多是 “第 i-1層的結點數目的2倍”，即 2*2^(i-2)=2^(i-1)，
如圖所示，當二叉樹確定在哪一層時，有一個唯一對應的結點最大數的存在，這種對應關系可以看作是函式關系，
滿足的關系式為：y=2^(i-1)（其中x為二叉樹中的某一層，y為該層的最大結點數）
最后通過驗證發現不管是在二叉樹中的那一層，層數和對應的最大結點數都滿足這個函式關系，所以該性質屬于二叉樹的特性，
性質2 深度為k的二叉樹至多有2^(k)-1個結點，(k≥1)
證明：一顆深度為 k的二叉樹最多含有的結點數，應該是該二叉樹中每一層上最多含有結點數的總和，
當深度為 k時，二叉樹的最大結點數為：2^0+2^1+2^2+…+2^(k-1) = 2^(k)-1，
性質3 對任何一棵二叉樹T，若其終端結點數為n0，度數為2的結點數為n2，則n0=n2+1，
證明：設 n1為二叉樹T中度為1的結點數，因為二叉樹中所有結點的度都不大于 2，得出二叉樹T結點總數為：n=n0+n1+n2，
度數為 1的結點表示它有一個孩子結點，度數為 2的結點有兩個孩子結點，樹中孩子結點的總數為：n1+2*n2，樹中只有根節點不是任何結點的孩子結點，因此二叉樹中的結點總數還可表示為：n=n1+2*n2+1，
根據兩個總結點數公式可得：n0=n2+1，
性質4 具有n個結點的完全二叉樹的深度為[log n]+1 或 log (n+1)，
滿二叉樹：一棵深度為 k且有 2^(k)-1個結點的二叉樹，圖中的 a就是滿二叉樹，
完全二叉樹：一棵深度為 k的二叉樹，其前 k-1層是一棵滿二叉樹，而最下面一層 (第k層)上的結點都集中在該層的最左邊的若干位置上，
上圖中的 b就是完全二叉樹，c不是完全二叉樹，
證明：假設二叉樹的深度為 k，根據完全二叉樹的定義，它的前 k-1層是深度為 k-1的滿二叉樹，共有 2^(k-1)-1個結點，因為二叉樹的深度為 k，二叉樹的結點數 n>2^(k-1)-1，由性質二可知 n≤2^(k)-1，所以有 2^(k-1)-1<n≤2^(k)-1，
由此可見，n個結點的完全二叉樹的深度為 [log n]+1，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/333788.html
標籤：其他
上一篇：0基礎C保姆自學 第二節——初步認識C語言的全部知識框架
下一篇：(C語言)實作常見排序的介面