第6章 樹狀結構

• • 前言
  • 6.1 樹
  • 6.2 二叉樹簡介
  • • 6.2.1二叉樹的定義
    • 6.2.2特殊二叉樹簡介
  • 6.3 二叉樹存儲方式
  • • 6.3.1數組表示法
    • 6.3.2清單表示法
  • 6.4 二叉樹的周遊
  • • 6.4.1中序周遊
    • 6.4.2前序周遊
    • 6.4.3後序周遊
    • 6.4.4二叉樹的周遊實作
    • 6.4.5二叉運算樹
  • 6.5二叉樹的進階研究
  • • 6.5.1二叉排序樹
    • 6.5.2二叉搜尋樹
    • 6.5.3線索二叉樹
  • 6.6 數的二叉樹表示法
  • • 6.6.1樹轉換為二叉樹
    • 6.6.2樹林轉換為二叉樹
    • 6.6.3樹與樹林的周遊
    • 6.6.4确定唯一二叉樹
  • 小結

前言

       數（tree）是另外一種典型的資料結構，可用來描述有分支的結構，屬于一種階層性的非線性結構。從企業的組織架構、家族内的族譜，再到計算機領域中的作業系統與資料庫管理系統都是樹狀結構的衍生運用。

6.1 樹

6.2 二叉樹簡介

       一般樹狀結構在計算機記憶體中的存儲方式以連結清單為主。對于n元樹來說，因為每個節點的分支都不相同，是以為了友善起見，我們必須取n為連結個數的最大固定長度，而每個節點的資料結構如下：

       需要注意，這種n元樹十分浪費連結空間。當n=2時，它的連結浪費率最低，是以為了改進記憶體空間浪費的缺點，我們最常使用二叉樹結構來取代樹狀結構。

6.2.1二叉樹的定義

6.2.2特殊二叉樹簡介

• 滿二叉樹

• 完全二叉樹

• 歪二叉樹

• 嚴格二叉樹

6.3 二叉樹存儲方式

       樹狀結構在程式中的建立與應用大多使用連結清單來處理，因為連結清單的指針用來處理樹相當友善，隻需改變指針即可。此外，也可以使用數組這樣的連續記憶體來表示二叉樹。至于使用數組或連結清單都各有利弊。

6.3.1數組表示法

6.3.2清單表示法

6.4 二叉樹的周遊

       二叉樹的周遊，最簡單的說法就是“通路樹中所有的節點各一次”，并且在周遊後，将樹中的資料轉化為線性關系。其實二叉樹的周遊，并不像之前所提到的線性資料結構般簡單，就以一個簡單的二叉樹節點而言，每個節點都可分為左右兩個分支，是以一共可以有ABC、ACB、BAC、BCA、CAB、CBA 6種周遊方法。如果是按照二叉樹特性，一律由左向右，就隻剩下三種周遊方式，分别是BAC、ABC、BCA。

這三種周遊方式的命名與規則：

中序周遊（BAC）：左子樹→樹根→右子樹

前序周遊（ABC）：樹根→左子樹→右子樹

後序周遊（BCA）：左子樹→右子樹→樹根

6.4.1中序周遊

6.4.2前序周遊

6.4.3後序周遊

6.4.4二叉樹的周遊實作

6.4.5二叉運算樹

6.5二叉樹的進階研究

       除了前面學習的二叉樹周遊方式外，二叉樹還有許多常見的應用，例如二叉排序樹、二叉搜尋樹、線索二叉樹。

6.5.1二叉排序樹

6.5.2二叉搜尋樹

6.5.3線索二叉樹

6.6 數的二叉樹表示法

       二叉樹隻是樹狀結構的特例，廣義的樹狀結構其父節點可以擁有多個子節點，稱這樣的樹為多叉樹。由于二叉樹的連結浪費率最低，是以可把樹轉換成二叉樹來操作，可以增加許多操作上的便利。

6.6.1樹轉換為二叉樹

6.6.2樹林轉換為二叉樹

6.6.3樹與樹林的周遊

6.6.4确定唯一二叉樹

小結

• 樹（tree）是由一個或一個以上的節點所組成的有限集合，具有樹根（root），其餘的節點分為n>=0個互斥的集合，T1,T,2,T3… …Tn,且每個集合稱為子樹。
• 每一個節點的上層節點為父節點，沒有父節點的節點為根節點。
• 子樹的個數為該節點的度，沒有子節點的節點，即度為0。
• 樹林是n個互斥樹的集合（n>=0），移去樹根即為樹林。
• 所謂祖先，是指從樹根到該節點路徑上所包含的節點，兒子孫則是在該節點子樹中的任一節點。
• 二叉樹（又稱knuth樹）是一個由有限節點所組成的集合，此集合可以為空集合，或由一個樹根及左右兩個子樹所組成。
• 如果二叉樹的高度為h，樹的節點數為2^h-1，h>=0，則我們稱此數為“滿二叉樹”（full binary tree）。
• 如果二叉樹的深度為h，所含的節點數小于2^h-1，但其節點的編号方式如同深度為h的滿二叉樹一樣，從左到右，由上到下的順序一一對應。
• 當一個二叉樹完全沒有右節點或左節點時，我們就把它稱為左歪斜樹或右歪斜樹。
• 二叉樹的每個非終端節點均有非空的左右子樹。
• 二叉樹的存儲方式可以使用數組或連結清單
• 以數組表示法來存儲二叉樹，如果越接近滿二叉樹，則越省空間，如果是歪斜樹則最浪費空間。
• 使用連結清單來表示二叉樹的好處是對于節點的增加與删除相當容易，缺點是很難找到父節點。
• 二叉樹的周遊（Binary Tree Traversal），最簡單的說法就是“通路樹中所有的節點各一次”，并且在周遊後，将樹中的資料轉化為線性關系。
• 中序周遊的順序為：左子樹→右子樹→樹根。
• 如果一個二叉樹符合“每一個節點的設局大于左子節點且小于右子節點”，這棵樹便稱為二分樹。因為二分樹便于排序及搜尋，二叉排序樹或二叉搜尋樹都是二分樹的一種。
• 使用連結清單建立的n節點二叉樹，實際上用來指向左右兩節點的指針隻有n-1個連結，另外的n+1個指針都是空連結。所謂“線索二叉樹”（Threaded Binary Tree）就是把這些空的連結加以利用，再指到數的其他節點，而這些連結就稱為“線索”（thread）。
• 在二叉樹的三種周遊方法中，如果有中序與前序的周遊結果或者中序與後序的周遊結果，可由這些結果求得唯一的二叉樹。不過如果隻具備前序與後序的周遊結果就無法确定唯一二叉樹。