DAY 06 : 樹


6.1 什麼是樹?

在這之前,我們都是在討論一對一的儲存結構,那如果碰到一對多的情形的話該怎麼辦呢?

樹是一種一對多的資料結構,是n(n>=0)個節點的有限集合。n=0時稱之為「空樹」,在任何一顆非空樹中會有以下的特性:

(請參照圖片編號)

圖6.1

  1. 存在著唯一一個根節點(Root)
  2. 沒有擁有任何子樹的節點稱為葉子節點(Leaf)或是終端節點(Terminal Node)
  3. 當n>1時,其餘節點可分為m個互不相交有限集合,而每一個集合本身就是一顆子樹
  4. 節點擁有的子樹數量稱為度(Degree),度為0的節點稱為葉子節點,而整棵樹的度是看各個節點中度的最大值,因此此圖上的樹的度就是3。
  5. 內部節點又稱為分支節點(Branch)非終端節點(Non-Terminal Node)
  6. 節點的子樹的根稱為孩子,孩子只會有一個雙親同個雙親的孩子之間為兄弟
  7. 樹中節點的最大階度就是樹的深度又稱作高度
  8. 階度是從根節點開始算起,根是第一階,以此類推。

6.2 樹的儲存結構(請參照圖6.1的樹狀結構)

樹中節點的儲存位置無法直接反映邏輯關係,和先前的線性串列不同,因此需要使用特別的方法才能夠展現出對樹的儲存結構的表示法。

6.2.1 雙親標記法

由於非每一個節點都有孩子,但每個節點一定都有雙親,運用這個特性,在每個節點中附設一個指標指向雙親節點在陣列中的位置

  1. 由於根節點沒有雙親,因此我們將根節點的指標欄設為-1
  2. |編號|data|parent|
    |0 |A |-1 |
    |1 |B |0 |
    |2 |C |0 |
    |3 |D |1 |
    |4 |E |2 |
    |5 |F |2 |
    |6 |G |3 |
    |7 |H |3 |
    |8 |I |3 |
    |9 |J |4 |
  3. 時間複雜度為O(1)
  4. 當找到parent=-1時就代表已找到樹的根。

如果再加上最左邊孩子欄(長子欄)便可得知節點的孩子是誰,再加上右邊兄弟欄便可以表示兄弟關係:

|編號|data|parent|firstchild| rightchild|
|0 |A |-1 |1 |-1 |
|1 |B |0 |3 |2 |
|2 |C |0 |4 |-1 |
|3 |D |1 |6 |-1 |
|4 |E |2 |9 |5 |
|5 |F |2 |-1 |-1 |
|6 |G |3 |-1 |7 |
|7 |H |3 |-1 |8 |
|8 |I |3 |-1 |-1 |
|9 |J |4 |-1 |-1 |

  1. 長子欄中若沒有孩子的節點則將指標設為-1
  2. 右邊兄弟欄中若沒有右邊兄弟的節點則將指標設為-1

6.2.2 孩子標記法

由於每一個節點可能有多個子樹,因此適合用多向鏈結串列,也就是讓每個節點有多個指標欄位,每個指標指向一顆子樹的根節點,這種方法就叫做多重鏈結串列標記法。不過因為樹的每個節點的度不一樣所以又可以設計成兩種方案:

  1. 指標欄位的個數等於樹的度
    一個節點會有一個資料欄位和多個指標欄位,指標欄位的數量取決於樹的度,以6.1的圖為例,這棵樹的度為3,因此每個節點就會有三個指標欄位,但是這個方法只適用於各節點的度相差很小的時候,不然很浪費空間。
  2. 指標欄位的個樹等於該節點的度
    當各節點的度相差很大時就適用這個方法。在這個方法中除了資料欄位和指標欄位外,還要有一個度欄位來儲存該節點的孩子節點個數,這樣子可以改善空間浪費但也帶來了時間的損耗
    不過如果再對每個節點的孩子節點建立單向鏈結串列作為儲存結構,就可以改善這個問題,為了這個方法需要再另外設計兩種節點結構,一個是孩子鏈結串列的孩子節點,具有資料欄位(儲存某個節點在陣列中的編號)和指向某一個節點的下一個孩子節點的指標欄位。另一種是陣列的首節點,具有資料欄位(儲存某節點資訊)和首指標欄位(儲存該節點的孩子鏈結串列的首指標)。
    孩子標記法的進階版:「雙親孩子標記法」,是將雙親標記法和孩子標記法結合的方法。

6.2.3 孩子兄弟標記法

任何一顆樹,其節點若有第一個孩子(左孩子)就是唯一的,右兄弟也是,運用這個特徵,我們可以設置兩個指標,分別為第一個孩子指標右邊兄弟指標,來幫助我們更方便去搜尋某個節點的某個孩子。

#資料結構 #DataStructure #初學者





內容皆是閱讀完程杰的大話資料結構後所留下來的筆記,所以可能只對我自己有參考價值啊...但有興趣的人還是可以看一下啦 不過很不信的如果你是想要看資料型別的話,我全都沒放(滾啦 有畫粗體字的全都是我認為重點中的重點!還請大家多多指教了!!!

留言討論