[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語言-技巧篇》,冼鏡光著。

相關連結

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!
  • http://insectlin.wordpress.com 昆蟲

    我走到補習班了? XD

  • http://insectlin.wordpress.com 昆蟲

    我走到補習班了? XD

  • hmm

    真的有人在看這專欄嗎?
    純好奇@@
    不知這專欄的intended reader是哪個族群….

  • hmm

    真的有人在看這專欄嗎?
    純好奇@@
    不知這專欄的intended reader是哪個族群….

  • Solomon

    我覺得不錯呀。像我自己不是資訊科系的,但是有接觸。有時有一些東西還是需要有一些文章來做敲門磚。
    我是覺得讓一些初學或是自學的人有一個清楚的開始,會比較知道在做什麼。

  • Solomon

    我覺得不錯呀。像我自己不是資訊科系的,但是有接觸。有時有一些東西還是需要有一些文章來做敲門磚。
    我是覺得讓一些初學或是自學的人有一個清楚的開始,會比較知道在做什麼。

  • http://mmdays.com Mr. Thursday

    也許想跨領域的讀者會有興趣 ^_^

  • http://mmdays.com Mr. Thursday

    也許想跨領域的讀者會有興趣 ^_^

  • http://www.soft4fun.net 好手

    哈囉~~ MMDays 的各位,我是「硬是要學」的好手。

    因為研究所課業的需要,所以小弟這邊有一份問卷想要麻煩各位幫個忙填寫一下。問卷不會太長,大概只需要撥個3分鐘幫忙小弟填寫就可以了。

    不曉得MMDays能否幫忙推一下呢? 謝謝囉^^”

    問卷網址:http://blog.onlyone.idv.tw/survey/

  • http://www.soft4fun.net 好手

    哈囉~~ MMDays 的各位,我是「硬是要學」的好手。

    因為研究所課業的需要,所以小弟這邊有一份問卷想要麻煩各位幫個忙填寫一下。問卷不會太長,大概只需要撥個3分鐘幫忙小弟填寫就可以了。

    不曉得MMDays能否幫忙推一下呢? 謝謝囉^^”

    問卷網址:http://blog.onlyone.idv.tw/survey/

  • ksbcboy

    我也走到補習班了 XD??
    這不是前天我還在教學弟的東西嘛 ~”~

    那天突然學弟跑來問 Mid Order+Post Order 畫出Binary Tree
    該不會Mr. Thursday是補習班老師吧 XD
    期末考到了 這話題總有點敏感 哈哈

  • ksbcboy

    我也走到補習班了 XD??
    這不是前天我還在教學弟的東西嘛 ~”~

    那天突然學弟跑來問 Mid Order+Post Order 畫出Binary Tree
    該不會Mr. Thursday是補習班老師吧 XD
    期末考到了 這話題總有點敏感 哈哈

  • sntw

    那個各位科班出生的不好意思,
    讀者我一直想知道這個到底電腦是如何理解的
    * + 1 2 + 3 4
    因為 * 或 + 應該要有兩個東西餵給他,
    但是當前面沒有東西,而下一個東西非可運算的數值時,
    電腦不是應該把這樣的情況當成 error 嗎?
    又或者是遇到這種情況時,先有個什麼暫存的東西,
    然後條件符合才進行運算?

  • sntw

    那個各位科班出生的不好意思,
    讀者我一直想知道這個到底電腦是如何理解的
    * + 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 的話
    好像是先丟進stack

    4
    2 3 3
    1 1 + + + 7
    + + + 3 3 3 3
    * -> * -> * -> * -> * -> * -> * -> * -> 21

    印象中是這樣XD

  • 路人

    糟糕 會自動縮空白 全亂了= =

  • 路人

    糟糕 會自動縮空白 全亂了= =

  • shik

    餵給第一個加號的是1、2
    餵給第二個加號的是3、4
    餵給乘號的是+12、+34,也就是3、7
    這樣能理解嗎@@?

    下一篇會不會看到Big-O阿XD

  • shik

    餵給第一個加號的是1、2
    餵給第二個加號的是3、4
    餵給乘號的是+12、+34,也就是3、7
    這樣能理解嗎@@?

    下一篇會不會看到Big-O阿XD

  • http://www.wretch.cc/blog/wthomasu thomas

    圖文並茂的精闢解說
    謝謝

  • http://www.wretch.cc/blog/wthomasu thomas

    圖文並茂的精闢解說
    謝謝

  • http://mmdays.com/ Mr. Thursday

    一開始先把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)

  • http://mmdays.com/ Mr. Thursday

    一開始先把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)

  • http://mmdays.com/ Mr. Thursday

    有機會再另外寫一篇文章介紹stack(堆疊)這個資料結構
    就比較容易看懂了 ^^

  • http://mmdays.com/ Mr. Thursday

    有機會再另外寫一篇文章介紹stack(堆疊)這個資料結構
    就比較容易看懂了 ^^

  • sntw

    哇,真是謝謝各位解惑,我還以為以格主的發文速度,這篇會沉下去呢!

  • sntw

    哇,真是謝謝各位解惑,我還以為以格主的發文速度,這篇會沉下去呢!

  • http://mmdays.com/ Mr. Thursday

    希望這篇文章能夠有所幫助!

  • http://mmdays.com/ Mr. Thursday

    希望這篇文章能夠有所幫助!

  • http://www.vdi.idv.tw pcbill

    補充一下,tree 的特性還有必須要有一個根節點(root note),還有結構裡不能有 cycle。不然就是圖(graph)了,請參考 http://en.wikipedia.org/wiki/Graph_%28data_structure%29
    不過作為入門跨領域的參考文章,我想 Mr. Thursday 已經說得很清楚了。

  • http://www.vdi.idv.tw pcbill

    補充一下,tree 的特性還有必須要有一個根節點(root note),還有結構裡不能有 cycle。不然就是圖(graph)了,請參考 http://en.wikipedia.org/wiki/Graph_%28data_structure%29
    不過作為入門跨領域的參考文章,我想 Mr. Thursday 已經說得很清楚了。

  • http://mmdays.com/ Mr. Thursday

    謝謝pcbill的補充!

  • http://mmdays.com/ Mr. Thursday

    謝謝pcbill的補充!

  • Catsondbs

    話說當初學stack這個結構時是完全的不知所云,既不知道有甚麼用途,也不明白為何要這麼麻煩;
    直到後來學用tree來表示加減法時才恍然大悟,還目瞪口呆地佩服一開始想出來的人…

    早點看到這麼文章就好啦,對入門者來說真的很簡單易明~

  • Catsondbs

    話說當初學stack這個結構時是完全的不知所云,既不知道有甚麼用途,也不明白為何要這麼麻煩;
    直到後來學用tree來表示加減法時才恍然大悟,還目瞪口呆地佩服一開始想出來的人…

    早點看到這麼文章就好啦,對入門者來說真的很簡單易明~

  • Pingback: » MMDays - Mr. Thursday - 二元樹在排序的應用

  • Pingback: » MMDays - Mr. Thursday - Stack堆疊的資料結構

  • 讚的啦

    像我這種非資訊出生,卻又是幹IT Coding行業的,一碰到這種比較深入的原理還真的是頭痛到不行,雖然不懂也是無所謂,但就是很想知道為什麼,卻又不可能去拿一本資料結構來K,這一篇就很適合我這種類型讀者的教材。最近深入C#與C++結合時候看到一個教材提這類東西還真像是瞎子在摸象,這篇總看完後就比較有大體的概念啦~~

  • 讚的啦

    像我這種非資訊出生,卻又是幹IT Coding行業的,一碰到這種比較深入的原理還真的是頭痛到不行,雖然不懂也是無所謂,但就是很想知道為什麼,卻又不可能去拿一本資料結構來K,這一篇就很適合我這種類型讀者的教材。最近深入C#與C++結合時候看到一個教材提這類東西還真像是瞎子在摸象,這篇總看完後就比較有大體的概念啦~~

  • El SKY

    真的很驚訝說~
    今天要考計概了~還有一些小地方不太懂~想說上網GOOGLE一下~
    就很巧的進來這個專欄~

    真的很開心喔~~這裡的說明很好懂~讓我受益良多喔~

    作者辛苦摟~

  • El SKY

    真的很驚訝說~
    今天要考計概了~還有一些小地方不太懂~想說上網GOOGLE一下~
    就很巧的進來這個專欄~

    真的很開心喔~~這裡的說明很好懂~讓我受益良多喔~

    作者辛苦摟~

  • Lily

    好棒喔!!這篇文章 前序中序後序的解釋很清楚!!! 作者GJ!!!