基本觀念
二元樹（Binary Tree）是一種樹狀的資料結構，每個節點可以儲存3筆資料，包含數據本身（data）、左指標（left）、右指標（right）。見下圖
所謂的子節點是指從同一個節點延伸出來的節點，以上圖為例，點7和點10是從點9延伸出來的，那我們就會稱點7和點10為點9的子節點，而點9為它們的父節點，點7和點10互為兄弟節點。
建立二元樹
建立二元樹需遵守以下兩個規則
- 先建立根節點
- 接著插入的新數據，如果數據比目前的節點大，則向右邊節點送，若比目前小則向左邊節點送，直到送到的位置沒有子節點則建立該節點
接著只要不斷重複規則2即可完成二元樹的建立，見下圖
假設我們要建立的數據為12、8、9、3、10、4
（1）建立根節點
（2）8<12，向左
（3）9<12，向左；9>8，向右
（4）10<12，向左；10>8，向右；10>9，向右
（5）4<12，向左；4<8，向左；4>3，向右
以上這顆二元樹就建立完成
二元樹刪除節點會遇到以下三種情況
一、刪除的是葉節點
這種情況因為沒有子節點，所以直接刪除即可。
二、所刪除的節點有1個子節點
這種情況也很單純，將欲刪除的節點刪除，並將它原本的子節點移動到它的位置取代它，就完成了。
三、所刪除的節點有2個子節點
有2種方法可以使用我們用下面這張圖舉例
方法一：從左子樹找最大節點
以上圖為例，假設我們要刪除的是節點8，8的左子樹里最大的是節點4，將4移動到原先8的位置就可以了，另外如果節點4下面也有子節點，則重複執行刪除節點的步驟就可以了。
方法二：從右子樹找最小節點
一樣以上圖為例，假設我們要刪除的是節點8，從節點8的右子樹中，最小的是節點9，我們將節點9取代節點8的位置就完成了，一樣如果要移上去的節點下也有子節點，則重複執行刪除節點的步驟。
搜尋二元樹的數據
搜尋二元樹節點的方式跟插入有點像，從根節點開始和要找的節點比大小，目標節點如果比較大，就向右子節點走，如果較小，就向左子節點走。見圖
假設到最後沒有找到相同的子節點，則代表這個數據不存在。
二元樹的階層（level）與深度（depth）
通常根節點稱為第一層然後向下延伸，見下圖
而深度則是該子節點與根節點的最短距離，depth = level - 1，以上圖舉例，節點5的階層是第4層，深度為3。另外，在二元樹中每 i 層最多有
2^n 個節點，其中 n= i - 1
二元樹的分類
一、滿二元樹（full binary tree）
滿二元樹是指除了葉節點沒有子節點外，其餘每個節點皆有2個子節點，見下圖
二、完全二元樹（complete binary tree）
完全二元樹是指除了最深層外，每個節點都是滿的，最深一層可以從左到右連續有節點，不可以中斷，見下圖。
上面的這三棵樹都符合，下面的是不符合的
這樣有理解完全二元樹的概念嗎～至於為什麼會存在這種分類就與資料儲存有關
三、完美二元樹（perfect binary tree）
完美二元樹是指除了最深層的節點外，所有子節點都是滿的，見下圖
四、平衡二元樹（balanced binary tree）
平衡二元樹是指，每兩個節點的子節點深度相差小於等於1，見下圖
以這顆二元樹為例，以節點12為基準，左子樹深度3右子樹深度2，相差1
接著我們以節點9為基準，左子樹深度1，右子樹深度2，相差1，你可以檢查每一個節點，下方連結到的左右子樹的深度相差小於等於1，這棵樹就是平衡二元樹。接著我們舉一個不合格的例子
以節點12為基準，左子樹深度3，右子樹深度1，左右子樹相差2，不符合平衡二元樹的標準。
一、中序（inorder）列印
所謂的中序列印分為以下3個步驟
（1）從左子樹往下走，直到無法前進就處理此節點
（2）接著處理此節點的父節點
（3）接著往右子樹走，若右子樹無法前進則回到上一層
以這張圖為例
大家可以跟著數字走，數字變為紅色則列印出這個數字你會得到以下數列 9 10 12 14 17 19 剛好是由小排到大，另外中序列印因為處理的順序是左子樹（left, L）根節點（root, D）右子樹（right, R）所以簡稱為LDR。
二、前序（preorder）列印
前序列印是走到哪就列印到哪，遍歷的順序是往左子樹走直到無法前進，接著往右走，以這張圖為例
因為走到哪就處理到哪所以蠻簡單的，使用前序列印出來的結果是 12 9 10 17 14 19 而又因為處理的順序是先根節點、左子樹、右子樹，所以縮寫為DLR。
三、後序（postorder）列印
後序列印跟前序不同在於，根節點留到最後處理，先處理左子樹，在處理右子樹，當這個節點的兩個子節點處理完成後，再處理該節點，見下圖
使用後序列印出來的結果是 10 9 14 19 17 12 因為處理的順序是先左子樹、右子樹、根節點，所以縮寫為LRD
二元樹的時間複雜度
以上大概介紹完二元樹的概念了（累，因為這個主題有點龐大所以實作的部分留待後續在補，另外平衡二元樹在增減節點時，會遇到需要旋轉以維持樹的平衡，也請留待筆者後續補充。
