資料結構複習(八) : 樹

經過線性表的洗禮，我們終於來到資料結構的大章節 "樹" !! 樹結構是資料結構中最最重要的結構之一，讓我們開始吧 !!

<<倒掛的樹>> by用小畫家轉的

一、樹的定義

樹可以稱作是描述"層次"關係的一種數據結構，定義如下:

1. Tree事由N個節點(N>=0)所構成，當N=0為一個空樹
2. 樹有一個特殊節點叫Root ，也就是根結點，定義為r
3. 其餘節點可以組成M個小樹，M的Root與r相連，子樹之間不相交、迴路

隨便畫一顆樹

解釋一些樹的專有名詞:

1. 度(Degree) : 這個節點有多少子樹 ，例如C的子樹一棵”度”為一，樹的度為整體樹最大度，因此是4
2. 葉節點(Leaf) :度為0的節點，也就是端點，B、I、J、K
3. 子、父、兄弟節點 : 就是一個節點上面、下面、平行的關係
4. 層次(Level) : 規定根結點在1，其他+1，例如G在第三層
5. 樹的深度(Depth) : 所有節點中最大層次，此樹為 4，(高度也是這樣算不過改為最低葉節點為1，向上加)

二、二叉樹 (二元樹)

一種特殊的樹，每一個節點最多只能有兩個子節點，注意的是子節點有順序之分的。

二叉樹中又有一些比較特殊的二叉樹，例:

1. 完美二叉樹 : 除了葉節點外，其他節點皆有兩個子，也就是把每一層填滿的意思。
2. 完全二叉樹 : 不用全填滿，但是有按照順序擺下來的。

二叉樹有一些重要的數學，例:

1. 一個二叉樹第i層，最多可以擺放 (2^i-1) 個節點
2. 深度為K的二叉樹最多有 (2^k)-1個節點
3. 一個節點下標為N，則兩個兒子必然是2N，2N+1，4的兒子為8、9
4. 完全二叉樹深度為 LogN+1

三、二叉樹代碼

使用鏈表可以很簡單的表示二叉樹

typedef struct TNode* BinTree;
struct TNode{
  ElementType Data;
  BinTree Left;
  BinTree Right;
};

下一個章節就會講到如何運用二叉樹了。

參考資料:

1. 《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月
2. https://www.icourse163.org/course/ZJU-93001

資料結構複習(七) : 隊列 Queue

資料結構複習(九): 二叉樹遍歷與建立