1. 二叉樹

• 普通定義：在計算機科學中，二叉樹是每個結點最多有兩個子樹（≤2$\le 2$，節點沒有子樹，節點有一個子樹，節點有兩個子樹）的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。
• 遞歸定義：二叉樹 T$T$ 是定義在有限節點集上的結構，它或者不包含任何節點，或者包含三個不相交的節點的集合：
  
  • 一個根節點
  • 一棵稱為左子樹的二叉樹（遞歸定義，新的二叉子樹，高度較之－1）
    
    • 這里的左子樹，既然是一種二叉樹，則它或者不包含任何節點，或者包含三個不相交的節點的集合
  • 一個稱為右子樹的二叉樹；

2. 完美二叉樹（perfect binary tree，滿二叉樹）

• 定義1：所有葉子結點高度相同的二叉樹。（所有葉子結點高度相同，也即，所有葉子節點在同一層級，在最高一層）
  
  • 所有內部節點（非葉子節點），度為2。即所有內部節點均包含，左右兩個子樹；
• 定義2：高度為 k≥0$k\ge 0$ 且有 2k+1?1$2^{k+1}?1$ 個節點的二叉樹，稱為完美二叉樹；

3. 完全二叉樹（complete binary tree）

• 定義1：完全二叉樹從根結點到倒數第二層滿足完美二叉樹，最后一層可以不完全填充，其葉子結點都靠左對齊。
  
  • 所有內部節點度也為 2；
• 定義2：