二元樹與一般的樹不同的地方
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的右子點,求得一二元樹
關於作者
粉絲專頁
文章分類