iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 13
1
Software Development

擁抱「資料結構」的「演算法」系列 第 13

擁抱「資料結構」的「演算法」(13) - 二元樹後序走訪

前言

終於來到後序訪問了,對中序與前序有初步認識之後,今天會介紹後序訪問,及時如何在中序式與前後序式之間做轉換


專業知識 - 二元樹後序走訪 Postorder

後序走訪 Postorder

後序走訪順序:左子樹 → 右子樹 → 根節點,根節點在最後面,結果為:左右根,左子樹的順序一定會大於右子樹,重點就在於根節點的位置在哪邊

例如:中序式的3 + 5,使用後序式表達的話會變成 3 5 +,後序表達式:< 運算元1 > < 運算元2 > < 運算子 >
https://ithelp.ithome.com.tw/upload/images/20200926/20129841jWL38vU6yR.png

後序練習

使用昨天的中序式公式:6 ÷ 2 ( 1 + 2 ),以後序訪問二元樹,請先找到左邊的子樹,然後訪問順序為:左子樹 → 右子樹 → 根節點,左子樹訪問結束再處理右子樹,最後才處理樹根節點

https://ithelp.ithome.com.tw/upload/images/20200926/20129841Bp5kjPgZLx.png

最後的後序走訪結果為:6 2 ÷ 1 2 + *,這時候電腦就可以開始進行運算,讀取順序為由左往右,讀取資料的規則為:連續 2 個數字與 1 四則運算就會開始計算:

走訪結果與電腦計算過程:

  • 6 2 ÷ 1 2 + *
    一開始會先讀取到 6 2 ÷,電腦就會進行 6 ÷ 2 = 3 的運算

  • 3 1 2 + *
    接著會讀取到 3 1 2,但不符合連續 2 個數字與 1 四則運算的規則,所以繼續讀到 1 2 +,電腦就會進行 1 + 2 = 3 的運算

  • 3 3 *
    然後繼續由右往左讀取3 3 \*,電腦就會進行 3 * 3 = 9 的運算

  • 9
    最後就會得到答案 9

由上述可知,不管是前序或後序算式,其計算結果都是一樣的

二元樹走訪整理

走訪順序

  • 前序走訪(Preorder):根節點 → 左子樹 → 右子樹
  • 中序走訪(Inorder):左子樹 → 根節點 → 右子樹
  • 後序走訪(Postorder):左子樹 → 右子樹 → 根節點

表示式

  • 前序表示式:運算子 運算元 運算元
  • 中序表示式:運算元 運算子 運算元
  • 後序表示式:運算元 運算元 運算子

一起來看看 4 + 5 * 6 - 3 + 1 / 2 的二元運算樹,其中的訪問順序可以參考下圖,要記得每種訪問的順序,而且左子樹優先權大於右子樹,尤其中序後序一定要先找到最下層的左子樹做為起始點,而前序則直接從樹根為起始點

https://ithelp.ithome.com.tw/upload/images/20200926/20129841Tjp02ikBFK.png

另外訪問的路徑也很不同,如下圖紅線
https://ithelp.ithome.com.tw/upload/images/20200926/20129841cDAva1K1JC.png

一秒辨識中序、前序與後序

  • 中序 : 4 + 5 * 6 - 3 + 1 / 2最前面與最後面都是運算元
  • 前序 : + - + 4 * 5 6 3 / 1 2 ,最前面運算子
  • 後序 : 4 5 6 * + 3 - 1 2 / +最後面運算子

中序換成前序

首先,先把中序運算式準備好,然後括號也要括好,
例如:4 + 5 * 6 - 3 + 1 / 2
會變成 4 + ( 5 * 6 ) - 3 + ( 1 / 2 )
再變成 (4 + ( 5 * 6 )) - 3 + ( 1 / 2 )
再變成 ((4 + ( 5 * 6 )) - 3) + ( 1 / 2 )
再變成 (((4 + ( 5 * 6 )) - 3) + ( 1 / 2 ))

運算子取代掉前面的括號,並且把後面的括號刪掉,前序 : + - + 4 * 5 6 3 / 1 2
https://ithelp.ithome.com.tw/upload/images/20200927/20129841BbZFjuISr7.png

中序換成後序

運算子取代掉後面的括號,並且把前面的括號刪掉,後序 : 4 5 6 * + 3 - 1 2 / +
https://ithelp.ithome.com.tw/upload/images/20200927/20129841lSZyc6xwEX.png


今日小結

終於把二元樹的走訪講完囉,根據二元樹走訪或式根據中序式推算出前序後序,看似複雜但其實很簡單,一回生二回熟,多做練習就比較能得心應手囉


今日謎題

今天是假日,小美想撥首輕鬆愉快的歌曲,留下了暗示給她的男朋友
93 100 * 10 14 * + 13 + ,請問你能猜到是哪首歌嗎?

昨日解謎

謎題說明:掌握前序走訪的順序:根節點 → 左子樹 → 右子樹,先訪問樹根結點,如果發現左右子樹,要先處理左子樹,接著繼續處理左子樹裡面的樹根,一直到左子樹訪問完為止,最後在處理右子樹,最後的訪問順序如下圖紫色圖示:PREORDER(前序訪問的英文)

https://ithelp.ithome.com.tw/upload/images/20200926/20129841S9zgWsm6OI.png

https://ithelp.ithome.com.tw/upload/images/20200928/20129841lNrMuVfUk8.png


上一篇
擁抱「資料結構」的「演算法」(12) - 二元樹前序走訪
下一篇
擁抱「資料結構」的「演算法」(14) - 圖形 Graph
系列文
擁抱「資料結構」的「演算法」30

尚未有邦友留言

立即登入留言