擁抱「資料結構」的「演算法」(13) - 二元樹後序走訪
前言
終於來到後序訪問了，對中序與前序有初步認識之後，今天會介紹後序訪問，及時如何在中序式與前後序式之間做轉換
專業知識 - 二元樹後序走訪 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(前序訪問的英文)
留言
張貼留言