|
第5章 樹狀結構 樹 二元搜尋樹的應用
二元樹 決策樹
二元樹的儲存結構 平衡樹
二元樹追蹤 堆積樹
樹的二元樹表示法 B樹
引線二元樹
|
|
|
|
樹的定義(1)
5-1 樹 有一個特殊的節點稱「樹根」(Root)。
其餘節點分為n≧0個互斥的集合，T1,T2,T3…Tn，則每一個子集合本身也是一種樹狀結構及此根節點的子樹。 「樹」(Tree)是由一個或一個以上的節點(Node)組成，並具備以下特點：
所謂一棵合法的樹，基本上就是符合樹是由一個或一個以上的節點所組成，而且節點間可以互相連結，但不能形成無出口的迴圈。例如下圖就是一棵合法的樹：
|
|
|
|
樹的定義(2)
5-1 樹 以下則是與樹相關的基本名詞介紹：
分支度(Degree)：每個節點所有的子樹個數。例如像節點Ｂ的分支度為2，D的分支度為3，F、K、I、J等為0。
樹的分支度(Degree of a Tree)：樹中所有節點的最大分支度。
樹葉或稱終端節點(Terminal Nodes)：分支度為零的節點，如此圖中的K、L、F、G、M、I、J。
非終端節點(Nonterminal Nodes)：樹葉以外的節點，如A、B、C、D、E、H等。
子點(Children)：某節點所有子樹的樹根。例如：A的子點為B、C、D，B的子點為Ｅ、F。
|
|
|
|
|
5-1 樹 父點(Parent)：若X節點為Y節點的子點，則Y節點為X節點的父點。
兄弟(Siblings)：同一個父點的所有子點互稱兄弟。例如：B、C、D為兄弟，H、I、J也為兄弟。
階度(Level)：令樹根的階度為1，若某節點的階度為L，則其子點的階度為L+1。
高度(Height)：樹的最大階度。
樹林：是由n個互斥樹所組合成的，移去樹根即為樹林，如下圖所示：
|
|
|
|
|
5-1 樹 祖先(Ancestor)：所謂祖先是指從樹根到該節點路徑上所有包含的節點。
子孫(Descendant)：為該節點的子樹中所包含任一節點。例如：節點B的子孫為E、F、K、L。
範例 5.1.1
下圖是否為合法的樹狀結構？試說明之。
|
|
|
|
樹的記憶體表示法(1)
5-1 樹 對於一樹最大分支度為K的情況，不論任何一節點的分支度是否為K，我們都要取K為鏈結欄位個數的最大固定長度。節點的資料結構將會是：
其中ｋ之值可以視分支度大小，而有所變化，由於許多鏈結存有空指標，容易形成浪費。
例如有ｎ個節點及ｎ*ｋ個指標欄位的ｋ元樹而言，其實只有n-1的欄位(不含樹根節點)會儲存非空指標及n*(k-1)+1個空鏈結。
|
|
|
|
二元樹的定義(1)
5-2 二元樹 left及right代表指向左邊子樹和右邊子樹的指標，而data這個欄位乃是存放該節點(Node)的基本資料。 二元樹(又稱為Kunth樹，或有序樹(Order Tree))是由節點所組成的有限集合，這個集合若不是空集合，就是由左子樹(Left Subtree)和右子樹(Right Subtree)所組成。
其資料結構如下：
|
|
|
|
二元樹的定義(2)
5-2 二元樹 以下就針對樹與二元樹之間的比較作一完整分析：
1.樹不可以為空集合，但二元樹可以是空集合。
2.二元樹中的每一個節點分支度(Degree) d，必定0≤d≤2，但樹中的分支度d，只要d>=0即可。
3.二元樹中，子樹間有次序關係，但在樹中，子樹間則沒有次序關係。例如下圖(a)與(b)：
|
|
|
|
特殊二元樹簡介(1)
5-2 二元樹 歪斜樹(Skewed Binary Tree)
當一個二元樹，所有的節點都沒有左子樹(Left Child)或者都沒有右子樹(Right Child)時稱之。
|
|
|
|
特殊二元樹簡介(2)
5-2 二元樹 深度為4 ，共有24-1個節點 完滿二元樹(Full Binary Tree)
有一棵階度為k的二元樹，若正好有2k-1個節點樹時，則稱為完滿二元樹(Fully Binary Tree of k)，k≥0 。
|
|
|
|
特殊二元樹簡介(3)
5-2 二元樹 完整二元樹(Complete Binary Tree)
一個二元樹的深度為k，而其所含節點數少於2k-1個，但是節點編號順序和完滿二元樹一樣。
也就是從左到右，由上到下，一個接一個，如下圖(a)。
|
|
|
|
特殊二元樹簡介(4)
5-2 二元樹 嚴格二元樹(Strictly Binary Tree)
二元樹中的每一個非終端節點均有非空的左右子樹，如下圖：
|
|
|
|
陣列表示法
5-3 二元樹的儲存結構 以陣列表示法來儲存二元樹，如果此二元樹愈接近完滿二元樹，愈節省空間，如果是歪斜樹(Skewed Binary Tree)則最浪費空間。 例如下圖： 循序的一維陣列表示法：
|
|
|
|
串列表示法(1)
5-3 二元樹的儲存結構 是利用指標及鏈結串列來儲存二元樹。另外每個節點的結構如下：
例如下圖所示：
|
|
|
|
串列表示法(2)
5-3 二元樹的儲存結構 Node 使用鏈結串列來表示二元樹的好處是對於節點的增加與刪除相當容易，缺點是很難找到父節點，除非在每一節點多增加一個父欄位。
如果使用C++語言的結構指令，可寫成如下的宣告：
|
|
|
|
中序追蹤
5-4 二元樹追蹤 1.追蹤左子樹。
2.拜訪樹根。
3.追蹤右子樹。 void Inorder (btree ptr)
{
if (ptr != NULL)
{
Inorder(ptr->left); // 走訪左子樹
cout<data; // 走訪列印樹根
Inorder(ptr->right); // 走訪右子樹
}
} 如下所示：
中序追蹤的C++遞迴演算法如下：
|
|
|
|
前序追蹤
5-4 二元樹追蹤 1.拜訪樹根。
2.追蹤左子樹。
3.追蹤右子樹。 void Preorder (btree ptr)
{
if (ptr != NULL)
{
cout<data; // 走訪列印樹根
Preorder(ptr->left); // 走訪左子樹
Preorder(ptr->right); //走訪右子樹
}
} 如下所示：
前序追蹤的C++遞迴演算法如下：
|
|
|
|
後序追蹤(1)
5-4 二元樹追蹤 1.追蹤左子樹。
2.追蹤右子樹。
3.拜訪樹根。 void Postorder (btree ptr)
{
if (ptr != NULL)
{
Postorder(ptr->left); // 走訪左子樹
Postorder(ptr->right); // 走訪右子樹
cout<data; // 走訪列印樹根
}
} 如下所示：
後序追蹤的C++遞迴演算法如下：
|
|
|
|
後序追蹤(2)
5-4 二元樹追蹤 範例 5.4.1
請問以下二元樹的中序、後序以及前序表示法為何?
範例 5.4.2
請問以下二元樹的中序、前序以及後序表示法為何？
|
|
|
|
後序追蹤(3)
5-4 二元樹追蹤 範例程式：ch05_01.cpp
|
|
|
|
|
|
|
|
|
|
Copy the following code to your webpage or blog to embed this presentation:
<a href="http://www.slidefinder.net/特/特殊二元樹簡介/33005956" class="slidefinder">05</a>
<script type="text/javascript" src="http://www.slidefinder.net/scripts/embedded.js"></script>
<a href="http://www.slidefinder.net/特/特殊二元樹簡介/33005956" class="slidefinder">05</a>
Det3
<script type="text/javascript" src="http://www.slidefinder.net/scripts/embedded.js"></script>
Share this presentation:
Comments