樹—二元樹的介紹與走訪 - notesHazuya筆記長也

樹—二元樹的介紹與走訪

2018-03-06 22:06:05   資料結構

二元樹

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

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,閒暇之餘就記錄一些筆記。