[ 資料結構 小學堂 ] 樹狀結構導論 : 樹的二元樹表示法

前言 :
在介紹了許多二元樹的操作與內容後, 雖然二元樹只是樹狀結構的特例, 廣義的樹狀結構其父節點可以擁有許多子節點, 我們姑且把這樣的樹稱為多元樹. 由於二元樹的鏈結浪費率最低, 因此如果把樹轉換成二元樹進行操作, 就會增加許多便利.

樹化為二元樹 :
對於一般樹狀結構轉化為二元樹, 使用的方法稱為 “CHILD-SIBLING” (Leftmost-Child-Next-Right-Sibling) 法則. 以下是其執行步驟 :

1. 將節點的所有兄弟節點, 用平行線連結起來.
2. 刪掉所有與子節點間的鏈結, 只保留最左子節點的鏈結.
3. 順時鐘轉45度.

請參考下面範例實作, 就可以清楚知道原理 :


二元樹轉換成樹 :
既然樹可以轉換成二元樹, 當然也可以將二元樹轉換成數, 參考如下 :

This message was edited 2 times. Last update was at 30/04/2010 10:15:21