【複習整理】基礎資料結構(C語言):二元樹(Binary tree)

ZGM (Will)
Jul 21, 2022

--

本系列的文章,主要是讓自己快速複習資料結構。由於多年前在學校學的資料結構實作已印象模糊,腦海中只剩下相關的概念(唉~久沒複習蠻容易還給老師的),因此透過在網路上觀摩別人的教學或閱讀書籍,然後練習與整理成文章,達到快速複習的目標。

參考的教學如下:《動畫圖解資料結構(第二版)》,作者:李春雄C 語言學習筆記 : 二元樹
http://yhhuang1966.blogspot.com/2018/06/c.html?m=1
[軟體工程師雜談] 輕鬆搞懂資料結構: 樹(Tree)
https://youtu.be/xDwFMffqLbw

下面開始複習二元樹(Binary tree):

在開始複習二元樹之前,先來回顧樹狀結構,而樹(Tree)的應用例子有祖譜與政府組織圖等。

樹(Tree)是由一個(含)以上的節點所組成的有限集合,其至少有一個根節點(Root node),若有根節點以外的節點,可分成一個(含)以上的互斥集合,即為根節點的子樹(Subtree)。樹可視為圖(Graph)的一種特例,即為一種無迴路(Loopless)的無向圖形(Undirected Graph)。下圖是一個高度為3的樹。

樹狀結構(重畫自引用資料)

樹的相關名詞解釋:
● 節點(Node):一筆資料即為一個節點,如上圖的A~F皆為節點。
● 父節點(Parent):節點的上一個節點,即為該節點的父節點,如上圖的A為B~D的父節點。
● 子節點(Children):節點的下一個節點,即為該節點的子節點,如上圖的B~D皆為A的子節點。
● 根節點(Root node):樹的最上層節點(無父節點者),如上圖的A即為根節點。
● 葉節點(Leaf node):無子節點的節點,,即為葉節點,又稱為終端節點(Terminal node),如上圖的E~F皆為葉節點。
● 子樹(Subtree):節點以下並且相連的樹狀結構,即為該節點的子樹,如上圖的D–G為A的子樹。
● 樹林(Forest):除去根節點後,其互不相連的各樹狀結構,即為樹林。
● 階度(Level):節點在樹狀結構的階層位置,根節點的階度為 1。
● 高度(Height):樹的最大階度即為樹的高度。
● 分支度(Degree):節點擁有的子樹個數稱為該節點的分支度,上圖根節點的分支度為3。

二元樹(Binary tree)則為每個節點皆符合 0 ≤ 分支度 ≤ 2,並且有左、右子樹之分的樹。其可進一步分為下列幾種二元樹:

  • 斜曲二元樹(Skewed Binary tree):
    如下圖所示,只有左節點的樹為左斜曲二元樹(Left-skewed Binary tree),只有右節點的樹為右斜曲二元樹(Right-skewed Binary tree)。
斜曲二元樹(重畫自引用資料)
  • 嚴格二元樹(Strictly Binary tree):
    每個非葉節點皆有非空的左右節點之二元樹(如下圖所示)。
嚴格二元樹(重畫自引用資料)
  • 完滿二元樹(Full Binary tree):
    高度h(高度h ≥ 0)且具有(2^h) -1個節點的二元樹(如下圖所示)。
完滿二元樹(重畫自引用資料)
  • 完整二元樹(Full Binary tree):
    滿足下列條件(若且為若)的二元樹:
    ◎ (2^(h-1))-1 ≤ n ≤ (2^h)-1,其中n為節點總數、h為高度。
    ◎ 節點編號會跟高度h之完滿二元樹的前n個節點編號一致。
完整二元樹(重畫自引用資料)

由上述可以推知,「完滿二元樹」≥「完整二元樹」≥「嚴格二元樹」,因此完滿二元樹必為完整二元樹,但完整二元樹不一定是完滿二元樹。

二元樹基本上有兩種表示法:

  • 陣列(Array)表示法:
    如下圖所示,將高度h的二元樹視作完滿二元樹,接著規劃大小為(2^h)-1的陣列,最後依照順序將節點編號存入陣列。
二元樹陣列表示法(重畫自引用資料)
  • 鏈結串列(Linked list)表示法:
    如下圖所示,鏈結串列的節點結構包含左右兩個分別指向左右子樹的指標(LChild與RChild),以及中間儲存資料的空間。接著採用此節點結構用來表示二元樹。
二元樹鏈結串列表示法(重畫自引用資料)

二元樹的走訪有三種,分別為前序追蹤(Pre-order)、中序追蹤(In-order)與後序追蹤(Post-order)。

  • 前序追蹤(Pre-order):又稱為「深度優先搜尋(Depth-First-Search,DFS)」,其追蹤順序為樹根→左子樹→右子樹,即為從父節點開始走訪,接著往左子樹走,直到無法前進後,接續處理右子樹。
  • 中序追蹤(In-order):又稱為「對稱追蹤」,其追蹤順序為左子樹→樹根→右子樹,即先往左子樹方向到無法前進,再退回父節點,接著再走訪右子樹。
  • 後序追蹤(Post-order):又稱為「廣度優先搜尋(Breadth-First-Search,BFS)」,其左子樹→右子樹→樹根,即先往左子樹方向到無法前進,再往右子樹方向到無法前進,接著才退回父節點。

對照下圖與上述三種追蹤,該二元數的前序追蹤的順序為8→7→4→2→10→16→11,中序追蹤的順序則為4→7→2→8→16→10→11,後序追蹤的順序則為4→2→7→16→11→10→8。

前序追蹤、中序追蹤與後續追蹤的對照圖(重畫自引用資料)

實作完滿二元樹與其三種追蹤(改寫自引用資料):

對照圖與執行結果:

回到👉【複習整理】基礎資料結構(C語言):目錄

--

--