樹—二元樹的介紹與走訪

二元樹

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

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

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

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

左(右)斜樹

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

滿枝二元樹

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

完整二元樹

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

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

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

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

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

二元樹的表示方法

陣列

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

鏈結串列

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

二元樹的走訪

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

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的右子點，求得一二元樹