前言

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

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

後序走訪 Postorder

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

例如：中序式的3 + 5，使用後序式表達的話會變成 3 5 +，後序表達式：< 運算元1 > < 運算元2 > < 運算子 >

後序練習

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

最後的後序走訪結果為：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 的二元運算樹，其中的訪問順序可以參考下圖，要記得每種訪問的順序，而且左子樹優先權大於右子樹，尤其中序與後序一定要先找到最下層的左子樹做為起始點，而前序則直接從樹根為起始點

另外訪問的路徑也很不同，如下圖紅線

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

• 中序 : 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

中序換成後序

把運算子取代掉後面的括號，並且把前面的括號刪掉，後序 : 4 5 6 * + 3 - 1 2 / +

今日小結

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

今日謎題

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

昨日解謎

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