Tree 資料結構解析

Tree

Tree(樹) 是一種非線性階層式排列資料結構，因為具有樹狀結構，看起來像一個倒過來生長的樹。

樹狀結構的基本資料存儲單位是節點 (Node)。

節點(Node)

節點 (Node) 具有以下欄位:

1. 資料參照： 用來存儲對應的資料或是對應到資料的參考
2. 子節點 (child) ： 用來存儲指向下一個階層節點的指標。

每個 Tree(樹) 只會有一個起始點，

這個點叫作根節點 (root)。

每個 Tree(樹) 所有樹內的節點不會形成任何迴圈。

Tree(樹) 的節點類型

Tree(樹) 的節點類型除了根節點 (root) 還有以下幾種：

1. 樹葉節點(Leaf): 沒有子節點的節點
2. 家長節點(Parent): 當一個節點具有子節點，該節點是子節點的家長節點
3. 手足節點(Sibling): 具有同一個家長節點的兩個節點，彼此是彼此的手足結點(Sibling)

節點深度

某個節點 n 的深度代表，從根節點到節點 n 的路徑長度

Tree(樹) 的高度

從根結點到最長樹葉的路徑距離

Tree(樹) 的種類

Tree(樹) 的種類根據樹中任意子節點間是否有順序關係，分為

1. 無序樹：樹中任意子節點間沒有順序關係，也稱作自由樹
2. 有序樹：樹中任意子節點間有順序關係

有序樹根據子節點分佈狀態又可分為:

1. 二元樹： 每個節點最多含有兩個子節點
2. 霍夫曼樹：用於霍夫曼編碼，可以讓編碼長度最短的最佳二元樹。
3. B樹： 一種對讀寫操作進行最佳化的自平衡的二元搜尋樹，能夠保持資料有序，擁有多於兩個子樹。

二元樹種類:

• 完全二元樹(Complete Binary Tree)：對於一顆深度是 d 的樹，除了第 d 層外，其他個層的子節點個數都已達最大值，且由左向右緊密排列。
• 完美二元樹(Full Binary Tree)：所有葉節點都在最底層的完全二元樹

• 平衡二元樹(Balanced Binary Tree)(AVL樹): 任何節點的兩棵子樹的高度差不大於1的二元樹

• 二元搜尋樹(Binary Search Tree): 空樹或是對所有節點符合以下特性的二元樹:
  1. 其節點大於所有其節點左子樹的值
  2. 其節點小於所有其節點右子樹的值
  3. 左右子樹都是二元搜尋樹(Binary Search Tree)

用途

通常會透過有序樹來將輸入的數據有一些基礎的分類，用來快速查詢相關資料的資料做存取。

比如說，把串流數據依照二元搜尋樹的方式存儲就可以讓搜訊效率達到 O(logN)。