[MMDays專欄] 由樹的前序、中序、後序走法來談資料結構

Posted By Mr. Thursday

在以前的文章裡面有幾次有提到「演算法」(Algorithm),可以把他想程式完成一件事情所需要的步驟,可能包含重覆某些步驟、依照條件執行部份步驟、或是從頭到尾執行固定的步驟。然而演算法通常需要資料結構的配合。不是主修計算機的讀者,也許不知道資料結構是甚麼東西,即使我說資料結構的英文是 Data Structure,可能還是沒辦法了解「資料結構」代表的意思。簡單地說,演算法是完成一件事情的步驟,那麼資料結構就是這些步驟作用的物品,譬如說刮鬍子,可能要先插插頭,準備鏡子,然後開始刮鬍子。但是如果沒有插座,沒有鏡子,沒有刮鬍刀,或是沒有鬍子,這些步驟就沒有東西可以作用了。因此演算法和資料結構,有一點點類似軟體和硬體的對應,只不過資料結構並不是完全屬於硬體的角色就是了。接下來我們就來看一下某些資料結構,尤其是 (tree) 的結構,以及不同的拜訪順序,產生的效果。

 pre_order

 

上面就是一棵「」(tree)。所謂,就是由「」(node)和「連結」(link)所組成,演算法可能就是依照不同順序來走訪這棵樹,或是根據某個規則新增樹的節點,減少樹的節點,以及這些步驟的時間複雜度等等。上面看到的還是比較特別的樹,因為每個節點只有兩個枝子 (branch),所以是一個二元樹 (binary tree)。又因為我舉的例子,剛好三層裡面有7個節點,所以是一棵完全樹 (complete tree)。

下面就列出一棵樹的三種走法:前序中序、以及後序

 tree_order1

圖片裡面的號碼,就代表拜訪的順序,這邊為了簡化說明,所以樹只有三個節點。最左邊是前序,也就是現在這個節點最先拜訪,自己先拜訪,在分別拜訪左手邊和右手邊的節點。中間那棵樹就是中序,也就是自己中間拜訪,先拜訪左邊,接著中間拜訪自己,最後才拜訪右手邊的節點。最右邊的那棵樹,號碼代表後序,也就是說自己最後拜訪,左手邊和右手邊的子節點都先拜訪,接著最後才拜訪自己。不知道各位讀者看到這邊是否了解三種順序的差別呢?

接下來我們要看比較多節點的樹,在這之前,我們先把上面那張圖抽象化一下:

tree_order2

 上面這張圖的號碼順序,和前一張圖完全一樣,只是子節點從圓形變成了三角形。這是代表甚麼意思呢?原本在只有三個節點的樹裡面,上面那個節點,我們通常稱為「父節點」(parent node),下面兩個節點,我們通常稱為「子節點」(child node)。如果子節點的位置,不只一個節點,而是用相同的方式,一直很多層節點長下去,就會變成一棵「子樹」(sub-tree),而不是子節點了。這張圖的三角形,就代表是子樹 (sub-tree)的意思。

所以如果是不只三個節點的樹,拜訪的順序還是和只有三個節點的樹一樣,只不過我們遇到子樹的時候,就用遞迴 (recursive) 的概念來執行,也就是說,我們先把剛才執行到一半的東西存在腦海,然後重新來過,把我們新遇到的子節點當成一個新的父節點來看,然後依照剛才只有三個節點的拜訪順序來判斷要先走哪一個節點。如果依照這個方法,第一張只有三個節點的圖,以及第二張用三角形代表子樹的圖,我們把子樹展開來,就會變成如下面三張圖所示,這是有7個節點的樹的前中後序的走法。

前序 (pre-order)

pre_order 

中序(mid-order)

 mid_order

後序(post-order)

post_order

所以到目前為止,我們提到了演算法和資料結構的關係,我們介紹了「」這個資料結構,我們介紹了三種拜訪樹節點的方法:前序中序後序。不過前序中序後序,和電腦的運算有甚麼樣子的關係呢?假設現在我們把節點,當成電腦裡面儲存運算元(operator)和運算子(operand)的地方,那麼下面這個四則運算的式子,就可以用一棵樹表示:

 (1 + 2) * (3 + 4)

因為有先乘除,後加減的規則,所以上面的式子如果寫成

1 + 2 * 3 + 4 

 算出來是11,而不是正確答案21。接下來我們用二元樹來表達這個運算式(expression)

expression

我們如果用「中序」來拜訪這棵樹,就會得到下面這個算式

 1 + 2 * 3 + 4

結果非常接近人類使用的運算式表示方法,但是少了一個地方,就是「括號」!這樣子會造成電腦運算的結果錯誤!因此在電腦裡面,如果不想多設計一個括號的電路,又想要把四則運算藉由走訪一棵樹來算出結果,通常無論是「前序」或是「後序」,都可以得到正確的答案,而不需要括號的協助。下面我們寫一下用前序拜訪所產生的運算式:

* + 1 2 + 3 4

後序拜訪產生的運算式

1 2 + 3 4 + *

都是不用括號,就可以得到答案的運算是表示方法。

關於前序中序後序的其他演算法和資料結構問題,有興趣的讀者可以進一步閱讀下面這本書:《C名題精選百則-使用 C語言-技巧篇》,冼鏡光著。

相關連結

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!