1.4 Tree

由邊和節點構成的資料結構, 節點通常就是儲存資料的實體.

     o  -> root node
    / \
   o   o
  / \   \
 o   o   o -> 這層都是葉節點

常見術語

根: 樹的頂端節點, 一棵樹只有一個根

邊: 節點到節點的連接

路徑: 沿著邊, 從一個節點走到另一個節點, 所經過的節點順序稱為路徑

父節點, 子節點

節點, 葉節點(沒有子節點的節點)

度: 一個節點所包含的子節點數

子樹

層: 從根開始到指定節點的層數, 也稱為高度或深度

走訪: 按照某個特定的順序存取節點

關鍵字: 節點物件域中的某個屬性, 用來識別節點物件

二元樹

定義: 樹中的每個節點, 最多只能有兩個子節點

對二元樹的理解

1. 二元樹與樹的區別為:

   a. 樹中節點的子節點樹沒有限制, 而二元樹中限制節點數為不超過兩個

   b. 樹的節點沒有左右之分, 但二元樹的節點是分左右的

2. 二元樹有五種基本型態

   a. 空二元樹, 連根節點都沒有

   b. 只有一個根節點的二元樹

   c. 只有左樹

   d. 只有右樹

   e. 完全二元樹(complete binary tree): 若設二元樹的高度為h, 除了第h層外, 其它各層的節點樹都達到最大個數,

   第h層有葉節點, 並且葉節點都是從左到右依次排序, 此即完全二元樹

3. 滿二元樹(full binary tree): 除了葉節點外, 每個節點都有左右子節點, 且葉節點都處在最底層

4. 滿二元樹必為完全二元樹, 完全二元樹不必然為滿二元樹

5. 二元樹常被用作二元搜尋樹(Binary Search Tree, a.k.a BST), 二元排序樹, 二元堆(Binary Heap, a.k.a Heap Tree)

性質

性質1. 在二元樹的第i層上至多有2^(i-1)個節點

性質2. 深度為k的二元樹至多有(2^k)-1個節點

性質3. 對任何一顆二元樹T, 若其終端節點數量為n0, 度為2的節點數為n2, 則n0=n2+1

性質4. 具有N個節點的完全二元樹的深度為[log2以N為底]+1

性質5. 如果對一顆有n個節點的完全二元樹的節點按層序編號, 即從第1層到第[log2以n為底]+1層,

每層從左到右, 對任一節點i(1 <= i <= n)有:

a. 若i = 1, 則節點i是二元樹的根; 若i > 1, 則其父節點是[i/2]

b. 若2i > n, 則節點i無左子節點; 否則其左子節點是2i. 即該節點是葉節點

c. 若2i+1 > n, 則節點i無右子節點; 否則其右子節點是2i+1

d. 若i為奇數且不小於1, 則Ki的左兄弟編號是i-1; 否則Ki無左兄弟

d. 若i為偶數且小於n, 則Ki的右兄弟編號是i+1; 否則Ki無右兄弟