登入
首頁 所有文章 資料結構 樹—二元樹的介紹與走訪
長也   2018-03-06 22:06:05(1年前)    1595點閱   1喜歡  0收藏
樹—二元樹的介紹與走訪  

二元樹

二元樹與一般的樹不同的地方

1.二元樹有左右之分,一般樹則沒有

2.二元樹每一節點的分支度至多為2,一般樹則沒有此限制

 

而二元樹的左子樹和右子樹也可以是空集合,如下圖所示,A與B為兩棵不同的樹,A樹右子樹為空,B樹左子樹為空。

左(右)斜樹

左斜樹的右子樹為空集合,相反的右斜樹的左子樹為空集合。下圖為一左斜樹。

滿枝二元樹

滿枝二元樹滿足階度為K,含有2K-1個節點,就稱為滿枝二元樹。

完整二元樹

完整二元樹若排列方式與滿枝二元樹相同,但卻沒有滿足2k-1個節點,則被稱為完整二元樹

還有一些關於二元樹的特性:

1.一棵二元樹在第i階度的最多節點數量為2i-1,i>=1

2.一顆階度為k的二元樹,最多的節點數量為2k-1

3.假設n0表示二元樹的樹葉節點,n2表示分支度為2的節點,則n0=n2+1

二元樹的表示方法

陣列

在陣列的儲存方式中,我們將樹想像成滿枝二元樹,其第i階度有2i-1個節點,以此類推。下表是上面滿枝二元樹在一維陣列的表示方法。

 

A B D C G E F
第一階度 第二階度 第三階度

 

鏈結串列

陣列的表示方法較適合滿枝或完整二元樹,若用陣列儲存斜(區)樹則會浪費很多的空間,我們可以利用鏈結串列解決這個問題。

 

LLINK DATA RLINK

 

二元樹的走訪

如何拜訪二元樹的所有節點,有三種方式:

1.中序走訪:先走訪左子樹,然後樹根,最後是右子樹

2.前序走訪:先走訪樹根,然後左子樹,最後是右子樹

3.後序走訪:先走訪左子樹,然後右子樹,最後樹根

實際上,前中後是樹根被走訪的順序,中序樹根第二個被訪問,前序樹根則是第一個被訪問,後序樹根則是最後一個被訪問,而左右子樹都是先走訪左子樹再走訪右子樹。

以上圖為例,其各個走訪的結果如下:

1.中序:dhbeaficg,2.前序:abdhecfig,3.後序:hdebifgca

求出唯一的二元樹

如果給定一二元樹的中序-後序、或者中序-前序都可以求得唯一的二元樹,但是前序-後序則無法求得。

兩種方法只要先求得樹根,大致上就可以推出樹的型態

假設一樹之中序訪問FDHGIBEAC、前序訪問ABDFGHIEC,由於前序必定先訪問樹根,可直接求得A為該樹之樹根,得知A為樹根,則可由中序求得左子樹FDHGIBE、右子樹C,如下圖

 

 

之後可由前序推得B是FDHFI及E的父節點,由中序可以得知E是B的右子點,如下圖

 

再由前序得知D是FDHGI的父節點,由中序得知F是D的左子點,如下圖

 

最後由前序得知G是HI的父節點,由中序得知H是G的左子點,故求得一二元樹,如下圖

 

 

若給定一中序BCDAFEHIG、後序DCBFIHGEA,一樣先由後序得知樹根A,因為後序一定最後訪問樹根,再由中序得知BCD為A的左子點,FEHIG為A的右子點

 

 

之後由後序得知B為DC的父節點,再由中序得知DC為B的右子點(因為中序一開始訪問的一定是最左子點,又B為DC父節點,因此DC為B的右子點),而FEHIG的樹根則為E。

 

 

C為D的父節點,且D為C的右子點(後序先訪問D,因此D有可能是C的右或左節點,而中序先訪問C而不是D,可得知D為右子點),再由後序得知G為HI的父節點,且HI為G的左子點

 

 

由後序得知H為I的父節點,中序得知I為H的右子點,求得一二元樹

 

 

本文作者:長也

糾結與想不開的資管系學生,之前常碰PHP,現在常碰到的是Python,閒暇之餘就記錄一些筆記。

             

如要發表回覆,請先 登入

  3則回覆
  回覆於2018-03-07 17:52:17
回覆  #1

補充一下(?)

前序中序後序皆為深度優先搜尋(dfs),顧名思義以深度為優先遍歷節點,一般使用stack(堆疊)或遞迴實做

還有一種叫做"階序走訪",又稱廣度優先搜尋(bfs),會走訪完同層級所有節點才往下走訪,一般使用queue(佇列)實做

以文章圖為例,階序走訪順序為"abcdefghi"

 

還有陣列模擬樹,是從索引值為1開始,假設一節點索引值i,i*2為左子樹,i*2+1為右子樹

常見的二元樹有:完滿二元樹、完整二元樹、完美二元樹

完滿二元樹:除了葉節點(終端節點)以外,每個節點都有兩個子節點

完整二元樹:各層節點全滿,除了最後一層,最後一層若有子節點則全部靠左

完美二元樹:各層節點全滿,同時也是完滿二元樹和完整二元樹

長也   回覆於2018-03-08 20:11:29

我晚點補充由走訪劃出對應二元樹

長也   回覆於2018-03-12 12:05:10

已補上求出唯一二元樹