一看到樹大家會想到甚麼勒，我會想到野餐，好想出去玩歐歐歐☆^(ｏ´Ф∇Ф)o
沒想到資料結構裡面也有樹和森林吧，他其實像是模擬現實生活中的樹幹、樹枝和葉子的樣子
那接下來我們一起看看樹的奧妙!(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

Tree(樹)

樹狀結構

樹狀結構是一種是一種階層式的架構非線性結構，資料間的關係是上對下、下對上，而不是前後，在日常生活中時常會看到，例如：組織架構，籃球賽程、公司組織等，因為畫出來的外型很像樹，所以我們叫它樹狀結構。

定義

是由≥1個Nodes所形成的集合，不可為空，滿足:

1. 至少有1個特殊節點，稱為Root(樹根)
2. 除了Root以外的節點為互斥集合(disjoint)，集合稱為Root的子樹(subtrees)
3. 不會有迴路

相關名詞

(圖)
1.根節點或樹根(Root)：
位於樹狀結構的最頂端，上方沒有其他節點。例如:
2.父節點(Parent):
有下層節點，則為父節點，每個Node只有一個以內的父節點。例如：
3.子節點(Children):
有上層節點，則為子節點。例如：
4.兄弟節點(Siblings)：
有共同的父節點。例如：
5.祖先節點(Ancenstors):
指某節點到根節點之間所經過的所有節點，都是此節點的祖先節點。例如:
6.分支度(Degree):
指此節點底下所擁有的子節點樹。例如:
7.終端節點或樹葉節點(Terminal):
沒有子節點(下層節點)的節點。例如:
8.非終端節點(Non-terminal):
除了終端節點之外的其他節點，都是非終端節點。例如:
9.階層(Level):
位於樹狀結構的第幾層(root為第一層，其子節點為第二層，依此類推)。例如:
10.樹高(Height)或樹深(Depth):
樹的最大階層數。
11. 森林(Forest):
由≥0顆互斥的trees所形成的集合，可以為空。
例如:(圖)

Tree的表示方式

[法一]利用linked list直接表示

作法:假設Tree's Degree=k
所以Node structure
(圖)
例:
(圖)

分析:
最大缺點在於極度浪費linking space

說明:
假設n個nodes，Tree's Degree=k
則總共link數=n×k條，其中有用的(link≠Null)有n-1條(因為root不用被指)，所以浪費的(Null links)數目有n×k-(n-1)條
⇒浪費比例=nk-(n-1)/nk=n(k-1)+1/nk
≒n(k-1)/nk=(k-1)/k
所以k=2會最少

[法二]將Tree化成Binary Tree之後再表示

[法三]"child-sibling"方法

做法:Node

[法四]括號法

做法:以(父,子₁,子₂,...,子ₙ)括號方式表達父點與子點間的組成關係，且可以Nested(巢狀)
例:
(圖)
A(B(EF)C(GHI)D(J))
例2:
A(B(CD(E))F(GH)I(JK(L))M)畫出樹
(圖)