Posted By Mr. Thursday
在以前的文章裡面有幾次有提到「演算法」(Algorithm)，可以把他想程式完成一件事情所需要的步驟，可能包含重覆某些步驟、依照條件執行部份步驟、或是從頭到尾執行固定的步驟。然而演算法通常需要資料結構的配合。不是主修計算機的讀者，也許不知道資料結構是甚麼東西，即使我說資料結構的英文是 Data Structure，可能還是沒辦法了解「資料結構」代表的意思。簡單地說，演算法是完成一件事情的步驟，那麼資料結構就是這些步驟作用的物品，譬如說刮鬍子，可能要先插插頭，準備鏡子，然後開始刮鬍子。但是如果沒有插座，沒有鏡子，沒有刮鬍刀，或是沒有鬍子，這些步驟就沒有東西可以作用了。因此演算法和資料結構，有一點點類似軟體和硬體的對應，只不過資料結構並不是完全屬於硬體的角色就是了。接下來我們就來看一下某些資料結構，尤其是樹 (tree) 的結構，以及不同的拜訪順序，產生的效果。
上面就是一棵「樹」(tree)。所謂樹，就是由「點」(node)和「連結」(link)所組成，演算法可能就是依照不同順序來走訪這棵樹，或是根據某個規則新增樹的節點，減少樹的節點，以及這些步驟的時間複雜度等等。上面看到的還是比較特別的樹，因為每個節點只有兩個枝子 (branch)，所以是一個二元樹 (binary tree)。又因為我舉的例子，剛好三層裡面有7個節點，所以是一棵完全樹 (complete tree)。
下面就列出一棵樹的三種走法：前序、中序、以及後序。
圖片裡面的號碼，就代表拜訪的順序，這邊為了簡化說明，所以樹只有三個節點。最左邊是前序，也就是現在這個節點最先拜訪，自己先拜訪，在分別拜訪左手邊和右手邊的節點。中間那棵樹就是中序，也就是自己中間拜訪，先拜訪左邊，接著中間拜訪自己，最後才拜訪右手邊的節點。最右邊的那棵樹，號碼代表後序，也就是說自己最後拜訪，左手邊和右手邊的子節點都先拜訪，接著最後才拜訪自己。不知道各位讀者看到這邊是否了解三種順序的差別呢？
接下來我們要看比較多節點的樹，在這之前，我們先把上面那張圖抽象化一下：
上面這張圖的號碼順序，和前一張圖完全一樣，只是子節點從圓形變成了三角形。這是代表甚麼意思呢？原本在只有三個節點的樹裡面，上面那個節點，我們通常稱為「父節點」(parent node)，下面兩個節點，我們通常稱為「子節點」(child node)。如果子節點的位置，不只一個節點，而是用相同的方式，一直很多層節點長下去，就會變成一棵「子樹」(sub-tree)，而不是子節點了。這張圖的三角形，就代表是子樹 (sub-tree)的意思。
所以如果是不只三個節點的樹，拜訪的順序還是和只有三個節點的樹一樣，只不過我們遇到子樹的時候，就用遞迴 (recursive) 的概念來執行，也就是說，我們先把剛才執行到一半的東西存在腦海，然後重新來過，把我們新遇到的子節點，當成一個新的父節點來看，然後依照剛才只有三個節點的拜訪順序來判斷要先走哪一個節點。如果依照這個方法，第一張只有三個節點的圖，以及第二張用三角形代表子樹的圖，我們把子樹展開來，就會變成如下面三張圖所示，這是有7個節點的樹的前中後序的走法。
前序 (pre-order)
中序(mid-order)
後序(post-order)
所以到目前為止，我們提到了演算法和資料結構的關係，我們介紹了「樹」這個資料結構，我們介紹了三種拜訪樹節點的方法：前序中序後序。不過前序中序後序，和電腦的運算有甚麼樣子的關係呢？假設現在我們把節點，當成電腦裡面儲存運算元(operator)和運算子(operand)的地方，那麼下面這個四則運算的式子，就可以用一棵樹表示：
(1 + 2) * (3 + 4)
因為有先乘除，後加減的規則，所以上面的式子如果寫成
1 + 2 * 3 + 4
算出來是11，而不是正確答案21。接下來我們用二元樹來表達這個運算式(expression)
我們如果用「中序」來拜訪這棵樹，就會得到下面這個算式
1 + 2 * 3 + 4
結果非常接近人類使用的運算式表示方法，但是少了一個地方，就是「括號」！這樣子會造成電腦運算的結果錯誤！因此在電腦裡面，如果不想多設計一個括號的電路，又想要把四則運算藉由走訪一棵樹來算出結果，通常無論是「前序」或是「後序」，都可以得到正確的答案，而不需要括號的協助。下面我們寫一下用前序拜訪所產生的運算式：
* + 1 2 + 3 4
後序拜訪產生的運算式
1 2 + 3 4 + *
都是不用括號，就可以得到答案的運算是表示方法。
關於前序中序後序的其他演算法和資料結構問題，有興趣的讀者可以進一步閱讀下面這本書：《C名題精選百則－使用 C語言－技巧篇》，冼鏡光著。
相關連結
-
(Wikipedia) Data Structure, 資料結構, 数据结构
過去的今天：
- MySpace 對決 Facebook: 誰贏誰輸? - 2008
- 中國互聯網第 21 次報告: 中國網民迅速成長!? - 2008
相關推薦
 |
 |
訂閱 所有文章 (含專欄文章 + 產業新聞 + 其他文章)
我走到補習班了？ XD
真的有人在看這專欄嗎？
純好奇@@
不知這專欄的intended reader是哪個族群….
我覺得不錯呀。像我自己不是資訊科系的，但是有接觸。有時有一些東西還是需要有一些文章來做敲門磚。
我是覺得讓一些初學或是自學的人有一個清楚的開始，會比較知道在做什麼。
也許想跨領域的讀者會有興趣 ^_^
哈囉~~ MMDays 的各位，我是「硬是要學」的好手。
因為研究所課業的需要，所以小弟這邊有一份問卷想要麻煩各位幫個忙填寫一下。問卷不會太長，大概只需要撥個3分鐘幫忙小弟填寫就可以了。
不曉得MMDays能否幫忙推一下呢？ 謝謝囉^^”
問卷網址：http://blog.onlyone.idv.tw/survey/
我也走到補習班了 XD??
這不是前天我還在教學弟的東西嘛 ~”~
那天突然學弟跑來問 Mid Order+Post Order 畫出Binary Tree
該不會Mr. Thursday是補習班老師吧 XD
期末考到了 這話題總有點敏感 哈哈
那個各位科班出生的不好意思，
讀者我一直想知道這個到底電腦是如何理解的
* + 1 2 + 3 4
因為 * 或 + 應該要有兩個東西餵給他，
但是當前面沒有東西，而下一個東西非可運算的數值時，
電腦不是應該把這樣的情況當成 error 嗎？
又或者是遇到這種情況時，先有個什麼暫存的東西，
然後條件符合才進行運算？
* + 1 2 + 3 4 的話
好像是先丟進stack
4
2 3 3
1 1 + + + 7
+ + + 3 3 3 3
* -> * -> * -> * -> * -> * -> * -> * -> 21
印象中是這樣XD
糟糕 會自動縮空白 全亂了＝ ＝
餵給第一個加號的是1、2
餵給第二個加號的是3、4
餵給乘號的是+12、+34，也就是3、7
這樣能理解嗎@@?
下一篇會不會看到Big-O阿XD
圖文並茂的精闢解說
謝謝
一開始先把pre-order的expression的三項東西push到stack裡面
然後進行下面的步驟
(1) pop出三項東西，如果剛好是 運算子 接著 兩個運算元 則執行步驟(2) 否則執行步驟(3)
(2) 把這兩個運算元 依照運算子運算之後 push回stack裡面, 跳到步驟(4)
(3) 把步驟(1)pop出來的三項東西push回去, 繼續步驟(4)
(4) 如果stack裡面只剩下一個數字 就是答案,
否則繼續push expression裡面的下一個東西 然後重覆步驟(1)
依照這個方法 運算(1+2)*(3+4)的pre-order expression
* + 1 2 + 3 4
round 0:
STACK: (empty)
EQ: * + 1 2 + 3 4
round 1:
STACK: * + 1
EQ: 2 + 3 4
round 2:
STACK: * + 1 2
EQ: + 3 4
round 3:
STACK: * 3
EQ: + 3 4
round 4:
STACK: * 3 +
EQ: 3 4
round 5:
STACK: * 3 + 3
EQ: 4
round 6:
STACK: * 3 + 3 4
EQ: (empty)
round 7:
STACK: * 3 7
EQ: (empty)
round 8:
STACK: 21 (answer!)
EQ: (empty)
有機會再另外寫一篇文章介紹stack(堆疊)這個資料結構
就比較容易看懂了 ^^
哇，真是謝謝各位解惑，我還以為以格主的發文速度，這篇會沉下去呢！
希望這篇文章能夠有所幫助!
補充一下，tree 的特性還有必須要有一個根節點(root note)，還有結構裡不能有 cycle。不然就是圖(graph)了，請參考 http://en.wikipedia.org/wiki/Graph_%28data_structure%29
不過作為入門跨領域的參考文章，我想 Mr. Thursday 已經說得很清楚了。
謝謝pcbill的補充!
話說當初學stack這個結構時是完全的不知所云，既不知道有甚麼用途，也不明白為何要這麼麻煩;
直到後來學用tree來表示加減法時才恍然大悟，還目瞪口呆地佩服一開始想出來的人…
早點看到這麼文章就好啦，對入門者來說真的很簡單易明~
[...] 在〈由樹的前序、中序、後序走法來談資料結構〉文章裡面提到了演算法就像是做事情的方法，資料結構則是對應演算法可以運作的東西，譬如說刮鬍子有步驟一、步驟二、步驟三，但是要有刮鬍刀、插頭、以及鬍鬚，那些步驟才有運作的東西，甚至不同的刮鬍刀，也會讓同樣的步驟有不同的執行效率，或是連原來的步驟都要改變，譬如說不是電動刮鬍刀，原來步驟裡面插插頭的那一步，也就可以不用作了。演算法和資料結構之間的關係也是如此，譬如說排序的演算法，可以用不同的資料結構來實現，好的資料結構，可能某一種排序演算法最適合，對其他種排序演算法，可能反而讓速度變慢。 [...]
[...] 因此，之前在〈由樹的前序、中序、後序走法來談資料結構〉裡面提到的前序、中序、後序的走法，也可以透過遞迴加上堆疊的資料結構來完成！譬如說上面這棵樹，我們從樹根7開始，發現有分支就往下走，但是我們先不把樹根忘掉，因此把樹根7 push到堆疊裡面。接者按照同樣的方法，往樹葉的方向走，一直走到樹葉的部分 ，再按照先進後出的順序，把堆疊pop出來的東西印出來，就是後序走訪這棵樹的方式了！ [...]
像我這種非資訊出生，卻又是幹IT Coding行業的，一碰到這種比較深入的原理還真的是頭痛到不行，雖然不懂也是無所謂，但就是很想知道為什麼，卻又不可能去拿一本資料結構來K，這一篇就很適合我這種類型讀者的教材。最近深入C#與C++結合時候看到一個教材提這類東西還真像是瞎子在摸象，這篇總看完後就比較有大體的概念啦～～