擁抱「資料結構」的「演算法」(12) - 二元樹前序走訪
前言
對中序走訪有初步了解之後,要來介紹難度高一點點的前序走訪,其實走訪概念是雷同的,差別在於順序不同,還有走訪結果
人腦不容易判讀,但方便
電腦`進行判讀
生活常識
昨天我們提到的常用的計算機,在進行加法
或減法
時十分方便,但你有遇過乘法
或除法
的情況嗎?例如 1 + 2 + 3 * 2
,你覺得計算結果是9
還是12
呢?答案是9
,因為四則運算中有一個原則是先乘除後加減
,所以我們會習慣先進行 3 * 2 = 6 的部分,再將 1 + 2 + 6 就會得到 9,那如果你想要得到 12,那你的算式必須使用括號
,公式為 ( 1 + 2 + 3 ) * 2 = 12
之前有一道小學生程度的題目很紅,聽說大概有 4 成的人都答錯(包括我),請問你知道下列算式的答案會等於多少嗎?
6 ÷ 2 ( 1 + 2 ) = ?
有人覺得答案是 1 ,有人覺得答案是 9 ,哪一個是你心目中的答案呢?中序式很容易讓人類判讀,但像這樣的小學生題目,竟然也會有 4 成的人答錯,這樣人腦的可信度似乎沒有想像中的高,所以有時候還是要靠電腦來輔助驗算正確與否
而這題正確答案是 9 ,試著把括號
寫出來就很清楚了,因為我們都知道括號的地方要先運算
:
答案 9 的公式
( 6 ÷ 2 ) * ( 1 + 2 ) = 9
答案 1 的公式
6 ÷ ( 2 * ( 1 + 2 ) ) = 1
但題目並沒有給這麼多括號,所以要怎麼辦,到底是 9 對還是 1 對呢?當題目沒有明確給出括號時,那就是由左往右
計算,另外記得題目有給括號的地方要先算:
6 ÷ 2 ( 1 + 2 )
= 6 ÷ 2 ( 3 )
= 3 ( 3 ) = 9
專業知識 - 二元樹前序走訪 Preorder
接著我們來看一下,如果今天是請電腦計算6 ÷ 2 ( 1 + 2 )
這一題,會不會答對呢?
前序走訪 Preorder
複習一下昨天提到的前序走訪的順序:根節點 → 左子樹 → 右子樹
,根節點
在前面
,結果為:根左右,左子樹
的順序一定會大於右子樹
,重點就在於根節點
的位置在哪邊
例如:中序式的3 + 5
,使用前序式表達的話會變成 + 3 5
,表達式:< 運算子 > < 運算元1 > < 運算元2 >
前序練習
中序式公式:6 ÷ 2 ( 1 + 2 )
先將二元樹畫出來,如下圖,如果不懂二元樹數如何畫出來的,可以使用以下兩個小技巧:
將公式的
括號
配對好,記得明確將要先加減或後乘除
的地方括好
例如:( ( 6 ÷ 2 ) * ( 1 + 2 ) )
配對原則
就是兩個數字(左右節點)
搭配一個四則運算(數根)
再來我們要使用前序走訪
,取得走訪結果,要先從樹根
開始訪問,順序:根節點 → 左子樹 → 右子樹
,如果樹根結點下面有子樹
,則繼續往該子樹的樹根
往下訪問,先處理左子樹,再處理右子樹
最後的前序走訪結果為:* ÷ 6 2 + 1 2
,這時候電腦就可以開始進行運算,讀取順序為由右往左
,讀取資料的規則為:連續 2 個數字與 1 四則運算
就會開始計算:
走訪結果與電腦計算過程:
÷ 6 2 + 1 2
一開始會先讀取到+ 1 2
,電腦就會進行 1 + 2 =3
的運算÷ 6 2 3
接著會讀取到 6 2 3,但不符合連續 2 個數字與 1 四則運算
的規則,所以繼續讀到÷ 6 2
,電腦就會進行 6 ÷ 2 =3
的運算* 3 3
然後繼續由右往左讀取* 3 3
,電腦就會進行 3 * 3 =9
的運算9
最後就會得到答案9
囉
今日小結
透過前序的走訪結果,是不是有觀察到,電腦在運算過程中完全不需要考慮括號
與先乘除後加減的問題
,只要按著由右而左
,且讀取到連續 2 個數字與 1 四則運算
時再進行運算即可,另外在電腦實際計算時,透過程式實作還須要透過堆疊才能成功取得連續 2 個數字與 1 四則運算
,這個部分會在日後講演算法時會在討論到
今日謎題
你獲得加入超人團隊的機會,你必須通過考核才能加入,因為了預防機密外流,通訊過程都會使用二元樹前序訪問的方式,請問你能成功解密嗎?內容為一個單字
昨日解謎
謎題說明:使用中序走訪(Inorder):順序:左子樹 → 根節點 → 右子樹
,如果遇節點下面還有左子樹,那就要先走訪最下層的左子樹,要記得左子樹
的優先權
永遠大於右子樹
,處理完畢之後在再處理根節點,最後才是處理右子樹,走訪順序可參考下圖橘色圈圈的數字,數字由小到大看過去的話,最後結果就會得到:2零二01三壹4
,所以小美男朋友是想告訴小美:愛你愛你一生一世,你猜到了嗎?
留言
張貼留言