Re: [問題] 二元樹的追蹤

看板C_and_CPP (C/C++)作者rrosymoon (紫月)時間16年前 (2009/05/14 19:01)推噓1(1推 0噓 3→)

留言4則, 4人參與討論串2/2 (看更多)

※ 引述《rrosymoon (紫月)》之銘言： : 　請問一下二元樹的追蹤法，有沒有比較推薦的書本或是網頁 : 　的教學可以看呢？ : 　我借的三本資料結構的書，除了前序追蹤是從樹根開始往左 : 　走之外，其他的都看不懂他的追蹤過程，感覺跳來跳去的好 : 　難懂..QQ : 先謝謝大家了～:) 自回.. 在第五本書(Borland C++入門與應用徹底剖析)裡找到了比較好的　解釋..(▔▽▔") 前序列印(DLR-->樹根左節點右節點)：　　每個節點皆會比他的左邊子節點及右邊子節點先列印，而左邊　　子節點又比右邊子節點有更高優先順序。　中序列印(LDR)：就是列印樹狀結構，且以從小到大的方式列印。　後序列印(LRD)：　　就是在列印其某個節點前，一定要先印他的左節點，然後右節　　點，等到兩個子節點印完後，才列印此節點。　換個方式來說明，就是..DLR要先印出D，再印出L，如果L還有子　節點，就再往下移動，直到L下的所有子節點都印完，子節點的列　印也是照DLR的優先順序來印。L印完後，才印D的R，列印順序同　前面。 EX:(前序列印 DLR) 7 / \ 4 9 / \ / \ 3 6 8 12 / / \ 5 10 13 \ 11 按照DLR的優先順序，要先印出7，然後往它的左節點4移動，此時　把4看成新的根（子節點的根），按照DLR的規定，所以印出4，再　往4的左節點3移動，把它當成新的根，因此印出3。因為3底下沒　有子節點了，所以往上一層移動，回到4。　4往右邊有子節點6，移動到6，印出6，再往左下移動到5，印出5。　到此，7左邊的節點全部都印完了，所以改移動到右邊的節點9。　印出9，往左節點8移動，印出8，底下已無節點，回到上一層9。　往9右邊的節點12移動，印出12，再往左節點10移動，印出10。　因為10底下還有右邊的節點，所以往右邊節點11移動，印出11。到此10底下的節點都印完，回到上一層12。　12有右邊節點13，所以往13移動，印出13。　因此，最後的結果為 7 4 3 6 5 9 8 12 10 11 13 EX:(中序列印 LDR) 7 / \ 4 9 / \ / \ 3 6 8 12 / / \ 5 10 13 \ 11 類似DLR的原理，要印樹根7之前，要先印出左節點4，移動到4 ，此時4變為新的樹根，要印4之前，要先印出左節點3，所以移　動到3，此時底下已無節點，所以印出3，回到上一層4。　按照LDR的順序，節點4的L已經印完，再來是印樹根的部份，所　以直接印出4，接下來移動到右節點6，把6當新的樹根(D)，有左　節點5，因此先印5，才印6。此時7左邊的節點都處理完，所以回到7，印出7。　再來往9移動，印出8，再印9，往右移到12，移到10，印出10，　印出11，返回到12，印出12，最後印出13。　所以結果是..3 4 5 6 7 8 9 10 11 12 13 不用特別排序，印出來的結果就有排序的效果，滿神奇的～^_^ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.133.117.77