樹(Tree)的基本概念

• 節(jié)點、根結(jié)點、父節(jié)點、子節(jié)點、兄弟節(jié)點
• 一棵樹可以沒有任何節(jié)點,稱為空樹
• 一棵樹可以只有一個節(jié)點,也就是只有根節(jié)點
• 子樹、左子樹、右子樹

• 節(jié)點的度（degree）：子樹的個數(shù)
• 樹的度：所有節(jié)點中的最大值
• 葉子節(jié)點（leaf）：度為0的節(jié)點

• 非葉子節(jié)點：度不為0的節(jié)點

  
  
  樹形結(jié)構(gòu)

• 層數(shù)（level）：根節(jié)點在第一層，根節(jié)點的子節(jié)點在第二層，以此類推
• 節(jié)點的深度（depth）：從根節(jié)點到當(dāng)前節(jié)點的唯一路徑上的節(jié)點總數(shù)
• 節(jié)點的高度（height）：從當(dāng)前節(jié)點到最遠葉子節(jié)點的路徑上的節(jié)點總數(shù)
• 樹的深度：所有節(jié)點深度中的最大值
• 樹的高度：所有節(jié)點高度中的最大值

• 樹的深度等于樹的高度

  
  

有序樹、無序樹、森林

• 有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關(guān)系
• 無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關(guān)系，也稱為“自由樹”
• 森林：由m（m>=0）棵互不相交的樹組成的集合

二叉樹（Binary Tree）

• 二叉樹的特點
  每個節(jié)點的度最大為2（最多擁有2棵子樹）
  左子樹和右子樹是有順序的
  即使某節(jié)點只有一棵子樹，也要區(qū)分左右子樹

• 二叉樹是有序樹

  
  
• 二叉樹的性質(zhì)
  1.非空二叉樹的第i層，最多有2^i?1 個節(jié)點(i ≥ 1)
  2.在高度為h的二叉樹上最多有2^h?1 個節(jié)點(h ≥ 1)
  3.對于任何一棵非空二叉樹，如果葉子節(jié)點個數(shù)為n0，度為2的節(jié)點個數(shù)為n2，則有:n0 = n2 + 1
  1.）假設(shè)度為 1 的節(jié)點個數(shù)為 n1，那么二叉樹的節(jié)點總數(shù) n = n0 + n1 + n2
  2.）二叉樹的邊數(shù) T = n1 + 2 * n2 = n – 1 = n0 + n1 + n2 – 1
  3.）因此 n0 = n2 + 1

真二叉樹（Proper Binary Tree）

• 真二叉樹：所有節(jié)點的度要么為0，要么為2

  
  

滿二叉樹（Full Binary Tree）

• 滿二叉樹：最后一層節(jié)點的度都為0，其他節(jié)點的度都為2

• 假設(shè)滿二叉樹的高度為h（h ≥ 1），那么
  1.第i層的節(jié)點數(shù)量：2^i-1
  2.葉子節(jié)點數(shù)量：2^h-1
  3.總節(jié)點數(shù)量n

  • n = 2^h ? 1 = 2^0 + 2^1 + 2^3 + …… + 2^h-1
  • h =

• 在同樣高度的二叉樹中，滿二叉樹的葉子節(jié)點數(shù)量最多、中節(jié)點數(shù)量最多

• 滿二叉樹一定是真二叉樹，真二叉樹不一定是滿二叉樹

  
  

完全二叉樹

? 完全二叉樹:對節(jié)點從上至下、左至右開始編號，其所有編號都能與相同高度的滿二叉樹中的編號對應(yīng)
?葉子節(jié)點只會出現(xiàn)最后 2 層，最后 1 層的葉子結(jié)點都靠左對齊
?完全二叉樹從根結(jié)點至倒數(shù)第 2 層是一棵滿二叉樹
? 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹

完全二叉樹的性質(zhì)

• 度為 1 的節(jié)點只有左子樹

• 度為 1 的節(jié)點要么是 1 個，要么是 0 個

• 同樣節(jié)點數(shù)量的二叉樹，完全二叉樹的高度最小

• 假設(shè)完全二叉樹的高度為h（h ≥ 1 ），那么

  • 至少有2h?1 個節(jié)點(20+21+22+?+2h?2+1)
  • 最多有2h ? 1個節(jié)點(20+21+22+?+2h?1，滿二叉樹)
  • 總節(jié)點數(shù)量為 n
    ?2h?1
    ?h ?1≤<h
    ?h= floor() + 1
    ?floor 是向下取整，另外，ceiling 是向上取整

• 一棵有 n 個節(jié)點的完全二叉樹(n > 0)，從上到下、從左到右對節(jié)點從 1 開始進行編號，對任意第 i 個節(jié)點
  1.如果i = 1 ，它是根節(jié)點
  2.如果i > 1， 它的父節(jié)點編號為floor（i / 2）
  3.如果 2i ≤ n ，它的左子節(jié)點編號為 2i
  4.如果 2i + 1 ≤ n ，它的右子節(jié)點編號為 2i + 1
  5.如果 2i + 1 > n ，它無右子節(jié)點

• 一棵有 n 個節(jié)點的完全二叉樹(n > 0)，從上到下、從左到右對節(jié)點從 0 開始進行編號，對任意第 i 個節(jié)點
  1.如果 i = 0 ，它是根節(jié)點
  2.如果 i > 0 ，它的父節(jié)點編號為 floor( (i – 1) / 2 )
  3.如果 2i + 1 ≤ n – 1 ，它的左子節(jié)點編號為 2i + 1
  4.如果 2i + 1 > n – 1 ，它無左子節(jié)點
  5.如果 2i + 2 ≤ n – 1 ，它的右子節(jié)點編號為 2i + 2
  6.如果 2i + 2 > n – 1 ，它無右子節(jié)點