Aloha～！又是我少女人妻Uerica！這陣子家人住院，從急診到加護病房再到普通病房，看到形形色色的病人，不免讓我不停思考人生追求是什麼，每個生病的人都長一樣，一樣的病人服、一樣的病床、一樣的不舒服，完全看不出這些人有多少財富或多高的成就。但我能看到的是他跟家人或朋友感情好不好，有沒有好好對待自己的身體，所以要好好愛自己還有身邊的人啊！

好的來進入主題吧～！

樹 (Tree)

樹是一種階層關係的資料結構，分支型的結構就像樹幹與樹枝的關係一樣。生活中常見的例子有家族族譜、決策模型等。

樹的定義與特性

樹是由一個根節點(Root)開始發展，在樹狀結構中的最基本單位，稱為節點
(Node)，而分支出去的節點稱為子節點(Child)。樹是沒有環的結構，且任意兩節點間只有一個唯一路徑，若隨意刪除其中一個枝 (Branch)，就會變兩個樹。

• 節點 (Node)：樹狀結構中每一個資料元素都稱為節點。
• 枝 (Branch)：節點向下延伸擴展的所用到的枝。
• 根節點 (Root)：根節點具有唯一性，是整個樹狀結構最上層的樹根。
• 葉節點 (Leaf)：節點之下都沒有子節點稱為葉節點(像樹葉的葉子)。
• 非終端點 (Non-terminal Nodes)：除了葉節點外的其他節點。
• 祖先節點 (Ancenstors) 與子孫節點 (Descendant)：一個節點往上走一直到根節點之前，所經過的節點都稱為祖先節點。一個節點往下走，到葉節點前，每個經過的節點都稱為子孫節點。
• 父節點 (Parent)與子節點 (Child)：被分支的節點上方一個節點稱為此節點的父節點，而節點向下分支出的節點稱為子節點。如同父子關係般，父節點通常只有一個，子節點可以有一個或多個。
• 兄弟節點 (Siblings)：同一個父節點的其他節點，稱為兄弟節點。
• 分支度 (Dregree)：每個節點所擁有的子節點數。
• 階層 (Level)：從樹根開始，向下延伸的層級。
• 樹深 (Depth)：節點與節點間的距離。根節點深度為 0 。

樹的類型

一般的樹都是有序樹 (OrderedTree)，指樹中任意節點與子節點之間是有順序關係的，每個節點的子節點是從左到右有次序的，另外還有無序樹（UnoderedTree），又稱「自由樹」，樹中任意節點的子節點之間沒有順序關係。以下介紹的都屬於有序樹。

二元樹（Binary tree）

樹依照不同的分支度可以區分成很多種類，但在資料結構中最廣泛使用的樹狀結構是二元樹。二元樹是指樹中的每一個節點 (Node) 最多只分支出2個子節點，，即分支度小於或等於 2 。二元樹的節點所分支的子節點，在左邊的稱為左子樹 (Left Sub-tree)、右邊則稱為右子樹 (Right Sub-tree)。

依照分支與節點的不同，還有下列幾種表示：

歪斜樹(Skewed Tree)
樹的每個節點的分支都只有左節點，或都只有右節點。

嚴格二元樹 (Strictly binary tree)
指的是每個節點的子節點只能是 0 或 2 的二元樹，簡單來說就是除了葉節點以外，每個節點都有兩個子節點。

完滿二元樹 (Full Binary Tree)
又稱 Perfect Binary Tree ，如果樹的高度是 k 節點，那節點的個數就是 2 的 k - 1 次方，是具有最多節點的二元樹。除了葉節點外，每個節點都有兩個子節點。

完整二元樹 (Complete Binary Tree)
指的是在一個樹中，除了最後一層外，其餘的節點都有兩個子節點，且遵循由上而下、由左至右排列。

二元搜尋樹（Binary Search Tree）

二元搜尋數其實也算二元樹的一種，只是在節點的資料排列上有些需遵循的特性。二元樹搜尋樹的每一個節點值都不相同，而每一個節點的資料大於左邊的子節點、小於右子節點的資料值。若左右都沒有子節點則是該層的最大或最小值。

AVL樹 (Adelson-Velsky and Landis Tree)

AVL樹是屬於二元搜尋樹的一種，所以符合二元搜尋樹的所有特性。但除了二元搜尋樹的特性外，AVL還必須符合每一個節點的的左邊子節點的高度-右邊子節點的高度只能是 -1、0、1，所以 AVL樹 也是平衡樹的一種，此特性讓整個樹不會長歪，在搜尋時的速度會更快。

紅黑樹（Red–black tree）

紅黑樹也是二元搜尋樹的一種，且與 AVL 樹的作用類似，也是為了要保持樹狀結構的平衡，而紅黑樹遵循以下特性：

• 樹上的每個節點 (node) 只能是紅色或黑色
• 根節點 (root) 一定要是黑色
• 葉節點 (leaf) 一定要是黑色的空值 (NULL)
• 紅色節點的兩個子節點 (child) 一定要是黑色 (亦即不能有兩個紅色節點相連，注意：黑色節點的子節點顏色沒有限制)
• 從任何節點出發，其下至葉節點所有路徑的黑色節點數目要相同

參考資料：

[資料結構] CH8. AVL Trees

用JavaScript學習資料結構與演算法 8：樹、 二元搜尋樹

樹狀結構_維基百科

資料結構的樹與二元樹（Trees and Binary Trees）

演算法筆記:Tree

Red-Black Tree / 紅黑樹

紅黑樹（Red Black Tree）介紹

Binary Tree: Intro(簡介)

JavaScript 學演算法（十二）- 樹 & 二元樹

好的今天就到這邊啦～記得多關心身邊的人喔～明天見啦掰掰！