Lec13 資料結構 第八週課程

NYCU OCW
75粉絲
2 次觀看·2023年12月3日
Trees (2/6)
授課教師:資訊工程學系 彭文志老師
課程資訊:http://ocw.nctu.edu.tw/course_detail.php?bgid=9&gid=0&nid=412
授權條款:Creative Commons BY-NC-SA
更多課程歡迎瀏覽交大開放式課程網站:http://ocw.nctu.edu.tw/ 本課程同時收錄至國立交通大學機構典藏,詳情請見:
http://ir.nctu.edu.tw/handle/11536/108205
那我們開始上課了
那上禮拜五的時候
我們是講到 Binary Tree
然後 Binary Tree 的 Traversal
然後呢
這個 Tree Traversal 裡面呢
就是它對應到的
因為我們有三顆 Operation
NVR 這樣
那它有六種組合
那其中有三種是
反正是顛倒過來這樣
所以就事實上是隻有三種
NVR、LRV、VLR 這樣
那它所對應到的那個
Tree 它 Traverse 的順序呢
就是所謂的 In-order、Post-order
還有 Pre-order 這樣
一對一對一這樣
那 Level-order 的話呢
就是更簡單的這樣
就是從上到下
這就是所看到的
是 In-order
假設這一顆 Tree 給你們畫這樣
那它 In-order 的順序
就是 NVR
那注意一下就是它重點
就是在於說
就是給你一個 Root 這樣
L 的話就是
L 就是往左邊走這樣
那就是繼續往
走到什麼時候為止呢
走到不能夠走下去為止這樣
就是遇到了那個
比方說像這個地方的話
是遇到這個藍色 Node 這樣
它是怒我的這樣
那走不下去以後怎麼辦
對 走不下去了
對 就把自己這個 Node
比方說因為 A 嘛
它左邊走 往左邊走
走不下去了
好 那就停止了
那接下來要做的動作是什麼
就是做 V 的動作
V 的動作就是
把這個 Node 的資料把它印出來
就是要印
就是 V 這樣
所以你看
是一個 A 這樣
好 那
印完這個動作以後
要做 LVR 嘛
所以第三個動作是什麼
R 就是往右邊走這樣
那你看一下
這個地方它往右邊走
對 也是遇到一個怒喔
走不下去了
那所以怎麼辦咧
這個 Node 的 A
就已經被印出來過了
所以這個時候
就是要 return 到上一層這樣
那上一層的話是要看說
就是這個除字
它那時候是有呼叫
往左邊走
那所以
這個既然都已經被我們 traverse 完了
所以它就會 return 到它上一層
就是 A 是誰呼叫它的
那很明顯就是 A 是誰呼叫它的
就是這個呼叫它
那所以這個告訴你什麼呢
這一個除號
它往左邊走
它已經拜訪過了這樣
那也是一樣
它這就有一個 recursive 的概念
那拜訪過了
那接下來要做什麼事
V 把它印出來
那所以可以看到是除號
那印完以後呢
接下來往右邊走 R
對 往右邊走 R 這樣
那它看到這個時候
它沒有馬上就把它印出來喔
大家想像一下
它看到這個右邊的這個 Node 叫 B 這樣
那 B 呢
這個 Node 看到以後呢
它首先所要做的事情是什麼
往左邊走這樣
左邊它已經是空了
那回來這邊
那回來這邊以後呢
對 就是把自己的資料印出來
就是 B 就會被印出來這樣
那接下來做 R 的動作
好那 完了以後呢
對 R 它發現是 Node 這樣
完了以後就回到這邊來這樣
那回到這邊來以後呢
這代表是什麼
這一個除號的右半邊的 Subtree
都已經被拜訪過了
除號 Subtree 都已經被拜訪過了這樣
那所以呢
你可以想像一下就是
除號下面的
不管是左邊的 Subtree
或右邊的 Subtree
都已經被拜訪過了這樣
那所以呢 它就要 return 回來
就是要看除號誰呼叫它
那很明顯這除是這個陳呼叫它
所以這時候就是
因為 L 已經完了
那接下來就把這個印出來
那一直類推
所以就是大家知道就是說
它對應到 LnvR
那它意義是什麼這樣
那 preorder 的話呢
就是 Vlnr
然後就是 Vlnr
那 postorder 是 LnrV
level order 的話就是一層一層
那 implement 方式的話很簡單
就是一個 recursive code
就搞定了
那這個 inorder
這個 recursive code
其實以這為例
就是它是屬於
tree 的 member function 之一
那 tree 裡面
tree 的一個宣告裡面
其實就只有一個 pointer
要注意喔
就是 class tree 裡面
它只有一個 pointer
什麼是 pointer
那 pointer 就是 root 這樣
那接下來大家看一下
你看它的 tree 裡面的 inorder 的順序
自己呼叫自己 recursive
那現在丟進來以後
就叫 currentNode 這樣
那這三行指令
只要你遵循的
看它的順序
像 inorder 的話就是 LnvR
就是 currentNode
假設它是 currentNode 有值的話
接下來就 inorder
呼叫 inorder
拜訪它的著子數這樣
那這個就是對應到 Lnr
那它當然就是會 recursive 呼叫
那呼叫不能呼叫以後呢
就是剛才我們看到的那個
那它就把自己的值印出來
然後這個東西就是 R
就是 LnvR
那 inorder 到 preorder
就很簡單
就是 order 都不用改
印變成 pre 這樣
那這三行順序
置換一下
preorder 是什麼
就是先印出來
然後接下來再看著子數
所以你看 preorder 的話
cout 是第一行指令
那接下來就是 preorder 的
它的 left child 和 right child
就一直類推
這個大概跟你講
那個 detail 的 step
這個回去自己去研究一下
那這個只是叫
告訴你說
如果你在 debug 的時候
它那個 step by step
它是怎麼 run 這樣
那這個是 preorder 順序
就是像我說的
你看實在太簡單了
postorder 也是一樣
LnvR
那如果你不要用 recursive code 的話
你可以看到剛才的運作方式
如果不要用 recursive code 的話
你就可能要用 stack
就用一個 stack 去存放它
那存放什麼呢
就是它不是會一直往左邊走嗎
看到左邊它不會馬上把它印出來
它就是看到左邊
如果發現左邊有 node
是可以繼續走
它就把它 push 到 stack 裡面
那直到它走不下去了
走不下去了就是
pop out stack 出來
所以這個動作
它就是在做 pop 的動作
把 stack 的東西丟出來
丟出來以後把資料印出來
印出來以後呢
往右邊走
你看這是一直這樣
還是往右邊走這樣
這有沒有問題
那 level order 的話
就是用 q 的架構去存它
所以大家看一下
level order 其實很簡單
寫幾行指令就好
也是一樣
看到一開始的時候是 root
current node 就是 root
那接下來呢
假設你發現 current node 它不是空的
那就把值印出來
把它 cout 它的值出來
那印出來以後呢
接下來要做的事情是什麼
如果它的左指數
這一個 node 的左邊的 left child 是有值的
那就把它 put
就是把它加到 q 裡面
q.add 這樣
就是 current node 的 left child
所以這是左邊的
你可以想像說
假設我拜訪 root 了
那 root 拜訪完以後呢
它下面的左邊或右邊
如果有它的 child 的話
都會被放到 q 裡面
那順序
順序是先看左邊再看右邊
因為 level order 是由左到右
由左到右
這邊 left child
這邊右邊 right child
所以可不可以顛倒
這兩行可不可以顛倒
這兩個
都是放在 q 裡面
可不可以顛倒
不能顛倒
那 q 有什麼特性
first in first out
那如果你把右邊的放在
比左邊還
那你的 level order
就是由右到左
所以這是地方看
假設我們規定這個 level order 是
由左到右
這是不能顛倒的
那接下來就是
放到 q 裡面
把它的左右放到 q 裡面以後呢
接下來做完這件事
就把 q 裡面的第一個 node
把它抓出來
所以大家可以想像一下
就是你看
第一個是 current node 是加
那接下來呢
在 q 裡面會有放什麼
乘和一
那接下來呢
就是 q 裡面有兩個元素
第一個元素是乘
乘把它拋出來
那拋出來以後呢
這個乘下面的乘和 d
會被我們放到
放到 q 裡面
所以在
把這個乘丟出來
q delete 出來以後呢
看到乘 d
那它的 q 的順序
q 裡面的順序就是
你會看到
排在第一個位置的是 e
第二個位置的是乘
第三個位置是 d
那所以接下來它要做的事情就是
q 裡面的第一個把它
第一個就是 e
把它 output 出來
那好玩的是說
不是好玩
就是下面剛好是沒有任何的
就是它的 left 和 right child
所以 q 裡面就只有兩個 element
第一個 element 是乘
第二個 element 是 d
那接下來就把乘丟出來
看到是 true 和 c
就依此類推
有沒有問題
大家覺得寫程式有不有趣
有不有趣
像我自己本身的話
DS 已經大概有三四年沒教
可是我每次教都覺得很有趣
為什麼
每次看那個 code
你會覺得又不一樣的感受
就是有時候在寫論文
寫論文和做研究
不見得會動到 code
要注意一下
寫論文和做研究
不見得會動到 code
寫論文和做研究
主要是邏輯要對
邏輯要對
就是前因後果
這個 q question
就是 q 和 a
a 就是 answer
我每次都跟同學講
在做研究的過程
就是一個探索之旅
問一堆問題
回答這些問題
q a
然後接下來
把這些東西都搞清楚以後
就是寫 paper
把它陳述出來
就是 presentation
presentation 要對
其實我已經滿久沒寫 code 了
可是我每次看到這個 DS
就會勾發起想寫 code 的慾望
激發
因為我覺得寫寫 code 其實是不錯
寫 code
就是直接
你會看到這些 code 會動起來
有實際的效應
接下來我們再回來這邊
剛纔看到 in-order
post-order 和 pre-order 以後
大家就會想說
老師我為什麼要知道
traversal 的順序
其實我們在上禮拜五的時候
就有講過了
為什麼要知道順序
因為我是要知道 tree 的 structure
tree 的結構
那結構有什麼好處呢
你瞭解這個結構有什麼好處
那有時候你可能會
以後你在研究所
或者是演算法的時候
會給你一個問題
假設我有兩棵 tree
我叫你比較說
這兩棵 tree 是否相等
那這個還是很簡單
等一下我們再看
判斷它兩棵是否相等
那我也可以說給你兩棵 tree
它會問你說
這兩棵 tree 它是否相似
相似的話
這定義怎麼定
比方說 a 下面有兩個子孫
b 和 c 這樣
那另外一個叫 a
下面有兩個子孫
是 c 和 b 這樣
它 root 是一樣的
它的 child 順序不一樣
你覺得相不相似
這個是很主觀的問題
是一直拋出來
相似是一個很主觀的
為什麼很主觀
看相似的定義
有些相似的會問說
這棵 tree 它符合那個結構
它只有三個 node
tree 有三個 node
那這棵 tree 把它放在那個 tree 裡面
它就是 root 下面有兩個 child
從結構上它是很相似的
但是如果你再細看
假設我的相似是要更嚴苛
左右我都要認為是一樣的
那你就會認為說它不相似
雖然結構很像
那這就是在衍生出很多有趣的問題
你自己可以想想看
tree 有了比較相似型
那像剛才我們看到
是左右指數這樣
左邊右邊指數這樣
那你怎麼知道左右指數
它們像不像
或者它是不是相同
那很快速的方法是什麼
就把它們的 tree
就是透過 traverse
把它的 string 叫出來
那你可以很快速的去做一些
string 的 comparison
string 就是字串
那你有沒有學過
Longest Common Subsequence
Longest LCS
有沒有
字串
這邊出來 post order 或 pre order
都會有一個字串
那字串你可以去比較什麼
比如說
共同出現的字
或者是
它們的字的順序是否一樣
就諸如此類的
所以從測試這個 tree 是否相等
它還可以衍生出很多的問題
未來你會慢慢看到
那接下來我們就稍微來講一下
兩個很基本的 operation
就在 tree 裡面
假設你有 in order post order
pre order 的話
你可以很容易做到 tree 的 copy
copy 一個 tree 出來
那第二個測試它的是否相等
那這個的話就是
tree 的 copy 的動作
原則上它就會有一個
procedure 叫 copy
那我已經去給它指令是什麼
就是那個 tree 的 root
tree 的 root 就是丟給它
那現在大家看一下
這個是 tree 的 copy 的動作
那一開始的時候
它是 root
一開始的時候是 root
我們先要 copy 一個 tree
就是有一個 tree 叫 a
你要 copy 一個 tree a
到另外一個 tree
那一開始的時候
你會去判斷說
這個 root 它是不是 empty
binary tree
大家注意一下
binary tree 它有可能是 empty
什麼叫 empty
就 binary tree 它不是一個 class
它的這個 root 就是 no
但是你一旦宣告了
它就是一個 binary tree
那所以這個動作
就是在去測試一下
這棵 tree 是不是 empty
假設是 empty 的話
那這個方框框裡面的動作
都不用做了
就是直接 return 回去
那如果這棵 tree 的 root
它不是 empty 的話
那就要去做下面這件事
那下面這件事在做什麼呢
我發現它不是空的
我發現它是有值的
所以這個時候我要把這個 node
一開始的時候是 root
一開始例子來看是 root
所以我要把這個 root 的資料
copy 一份出來
那 copy 的話就會牽涉到
因為 copy
所以我要去跟這個系統
要一個 node 的空間
叫 tree node 的空間
叫 temp
那它是一個 new tree node
那 new 過來以後
我要到一個 temp 的空間
就是 tree node 的空間以後
接下來要做什麼事
接下來把資料值
original data
就是這個資料的 data
餵到 temp 的 data 裡面
然後第二個呢
就是去做 copy 的動作
這個 copy 的動作是什麼呢
copy 它的左邊的 child
你看它是呼叫 copy 的變數
這是左邊的 child
這是 temp 的 left child
那這個動作呢
會怎樣
它會 recursive 下去做
就是 root
它的 data 就是有了
那接下來它的 left child
它的 left child 可能會指到一個 subtree
大家這樣想
它的 left child 可能會指到一個 subtree
那所以呢
根據這個 copy 的 left child 的 subtree
它會做什麼事
它會往它的左邊指數
開始去做 copy
就是它的左指數
就是 left child 那個 node
會被呼叫
呼叫完以後呢
去判斷它是否是有值的
如果有值
它又去 create 一個新的 node
去把它叫做 left child
left child node
然後把 data copy 一份
然後呢
又往它的子孫
子孫繼續 copy 下去
所以這個的話
是第二行和第三行
希望同學發揮一下想像力
你覺得它不是一個 pointer
它不是立即的 pointer assignment
其實同學一定會說
老師那這樣很簡單啊
original left child 等於 time 的 left child
那你只能 copy 到
這個 tree 的 root 還有左右
那下面呢
沒辦法下去
所以要注意一下
就是說
這個 left child 和 right child
它是一個 procedure
是 recursive 的 procedure
它不是一個 assignment 的動作
所以做這個 recursive code
它可以把左邊的指數
和右邊的 subtree
都去做複製一份
這個請回去想一想
所以做完這個以後呢
這是一個 copy 就完成了
那同樣的
同學要想一下
這個地方
它跟你的 in order 有沒有很像
很像啊
這邊就是 v
這邊就是 l
這邊就是 r
v,l,r
那就是透過 in order
那所以呢
你可以自己在旁邊
寫一個問號
我可不可以用 pre-order
或 post-order
來達到 copy 的動作
我可不可以利用 pre-order
或者是 post-order
來達到 copy 的動作
為什麼要 in order
這個請大家回去想想看
所以呢
這是 copy
那接下來我們來看相等
等
就是兩顆 tree 要相等
那在這個地方的話
它做了一個
operation overloading 的動作
等等
就是以後如果你看到
等於
假設我宣告
兩顆 tree
一個 tree 叫 a
一個叫 tree b
你看到等於的話
等等
等於的話就是要執行這個指令
我要把它去 overload
那這個的話呢
就會有兩顆 tree
就是 x 和 t
我們要餵進去給它的是
兩顆 tree 的 root
然後
執行一個 procedure 叫 equal
equal
那
大家看一下
這個 equal
這程式怎麼 run
procedure equal
那兩顆
兩個 pointer
a 和 b
那它們都是 tree node 的 pointer
那
所以呢它做了這件事
這下面這件事情
那這下面什麼事呢
就是它當然是去判斷說
a 和 b 是否是
zero
就是空的
empty 這樣
那假設是空的話
就不用做比較了
就直接
你看這個要是 n 了
n 了
就是假設 a
它是 empty tree
b 也是 empty 的 binary tree 這樣
那這個式子就會增
那增的話呢
就直接
就 go back 回去
不用再做
任何 tree 的 traversal 這樣
對
那如果它不是空的呢
對
你就要做下面這個 if 這樣
對
這個 if 呢
對
很多框框喔
這同學要注意
首先呢
它先去判斷什麼呢
a 和 b
a
n 了 n 了 b 這樣
對
然後接下來還要 n 喔
就是 a 和 b
都需要有值這樣
那接下來要做的事情是什麼呢
在 n 呢
a 的資料要等於 b 的資料
這樣
對
然後呢
接下來還要再做一個 n 喔
這 equal
就是在 n 的裡面
就是在 if 的條件
這個 if 的條件非常多喔
在 if 的條件裡面
資料判斷相同
接下來去判斷
它的左邊的 child
left child 和 b 的 left child
是否相同這樣
好
那這同樣的
對
這個是一個 recursive function
對
就是 n equal
a 的 left child 是不是等於 b 的 left child
對
就是它不是
它不是那麼簡單就是說
a 的 left child 等於 b 的 left child 這樣
你只能會比一層
比一層
那這個呼叫這個 equal 的話
就是會
recursive 的去比較它的 subtree 這樣
就是會呼叫這個
所以
n n equal 這樣
然後再下來就是 n n
就是再去檢查
它的右邊的 child
是否相同這樣
是否相同
所以
這地方就是有幾個條件
一個條件 a
b
然後資料要一樣
左邊的要一樣
右邊的要一樣
是左邊的 subtree 要一樣
右邊的 subtree 要一樣
這種情況之下
都成立的情況之下
它才會是 true 這樣
所以這 if 的括弧
下面有好多
這邊至少有
就是一些條件的判斷這樣
那如果這些條件都成立的話
就 return 1
就是它是真的這樣
那
這叫做
做 equal 這樣
就是
判斷 a 是不是等於 b
這沒問題
有沒有問題
沒問題喔
確定
對
這很簡單
你看這 equal 竟然這麼簡單
對
就是隻要一個 if 嘛
對
裡面都沒有什麼 statement 耶
對
weird statement 就是呼叫 equal 這樣
放到那個條件去做判斷這樣
所以我覺得 equal 是很簡單
就是做 similar
判斷兩顆 tree 是否相似
這個
比這個難多了
相似性
就不可能是這樣 M 啦
對
它有一種做法就是把它
就像我剛剛一直在講的
就是把 output 變成一個 string
從 string 的角度來去看它是不是 equal 這樣
好
其實後面
應該會有一個
習題啦
就是
對
老師你說
變成 string
對
變成一個 string
比方說這顆 tree 這樣
變成一個 string
叫 inorder 的 string
或 preorder 的 string
還有 postorder 的 string 這樣
那接下來其實我們可以
在這地方就是給
同學一個預告
預告什麼呢
我們問你一個問題喔
假設我給你一顆 inorder 的 string 的話
它是不是能夠決定
唯一的 tree
對
假設我給你
就是這顆 tree
它有它對應到的
inorder
preorder
還有 postorder 的 string 這樣
好
那如果我給你
只是其中的一個 string
就比方說 inorder 的
這個 traverse 的 string
對
那它的 tree
是不是
只會長成這樣
而且是唯一的
對
那這個意思就是說
對
你必須要
可能要去證明一下
就是
這兩顆 tree
它們的結構
長得不一樣
但是有同樣的
inorder 的順序
對
所以
這是一個預告啦
因為後面他會
會講說
對
就是
要決定唯一的
唯一的這個 tree
對
不能夠光靠
就是這三個裡面的
就是單獨只考慮一個
就是它 traverse 的順序這樣
好
這是預告
請同學再注意一下
就是後面會講
好
那接下來大家看一下
就是
另外一個重點
那另外一個重點的話呢
就叫 calculus 的 expression 這樣
那 calculus expression 的話
是在說什麼事情
反正就是去做一些邏輯的判斷
好
那這邊就是
有
有幾個 operation
可能要注意一下
因為這個
這個叫 not
是 not
那這個呢
叫做 and 這樣
那這個呢
叫做 or 這樣
or
那大家都有學過 boolean function 嘛
boolean
那現在呢
就要問你說
那
這個式子叫 boolean
這是個 boolean function 這樣
那 x1
x2
x3
它所
對應到的數值
有可能就是
true 或者是 false
其實只有兩個
就 1 或者是 0 這樣
那所以呢
這個 problem 叫什麼呢
這個 problem 就是說
如果給你這樣一個 expression
那
你可不可以告訴我
有沒有任何的 assignment
有沒有任何 x1 x2 x3
的 assignment 的組合
會使得這個式子是 true 這樣
就這個問題
這有沒有問題
有時候你做一個電路啊
這邊 x1
弄一個電路這樣出來這樣
對 也許呢
你的電路的 boolean
寫得不好這樣
那這個燈呢
它永遠不會 output 是 1 這樣
假設我們設計一個
就是開燈
開燈的裝置這樣
那 1 的話
就是電流就會被啟動
那就有電燈會亮
然後 0 的話就沒有
對 那
你可能也會想去問說
這一串式子
我所提供這些條件是
有沒有可能
它在某一個組合
某些組合裡面
就是它會 true 這樣
就會開燈
對 這是開燈這樣
那這就是它的 problem 這樣
那這個 problem 的話呢
我們可以再想想看
假設我給你更
這一長串的 boolean expression 這樣
那總共有幾個變數
x1 x2 x3
總共有三個變數
那這三個變數呢
這個左半邊所看到的
就是它的表示方法
是一個 true 的表示方法
那同學回去
就在旁邊寫一下
就是回家
你要去看一下書這樣
看什麼書
就是從這個式子
怎麼變成這個 true
從這個式子
怎麼變出那個 true 的表示方法
請你回去閱讀一下書
就是看一下教科書這樣
因為其實還滿簡單的
那這個我們就不講了
那所以呢
有三個變數
x1 x2 x3
那三個變數
那每個變數都可能是 true 和 false 這樣
它有幾種排列組合
2的三次方
就是2的三次方
就是因為三個變數嘛
那每個變數都有 true 或 false
它總共有三個
2的三次方
就八種組合這樣
那八種組合
那接下來要做的事情是什麼
2的三次方
八種組合嘛
那接下來我要做的事情就是
把每一種組合
比方說 TTT
就餵進去這個
這個式子裡面
餵進去這個式子裡面
讓我們看它的結果
是不是 true 這樣
那這個要裝幾次
就以這個例子來看的話
就 fold 回一圈
裝八次這樣
那每一次餵給它
不同的設定
x1 x2 x3 這樣
就結束了
這沒問題
這邊也沒問題喔
那接下來最後問同學說
那怎麼樣去
怎麼去叫電腦
對
我餵進去參數
就是第一個參數叫 TTT
s1是1
s2也是1
s3也是1
那我們現在要去
餵進去讓電腦
能夠自動判斷
這個式子
它是
它的值是什麼
是 true 或是 false 這樣
要怎麼達到這件事
你說老師
是不是用你自己人腦
去做很快這樣
但是我們其實不要人腦
我們要電腦
要怎麼做
給大家一個 hint
就是
之前我們是不是有學過
這是 expression
2加3乘上4
有沒有
在 link list
就是2加3乘上4
在 stack 還是
stack 那個地方
我們是不是有講過
對
它是不是一個
多項式的 evaluation
對
那這跟多項式 evaluation
一不一樣
對
加減乘除
對不對
是很像
除了
除了什麼
加減乘除
要變成什麼
就是
not and
or
三個 operator 這樣
那
多項式那個
就是要 evaluate
那個值是多少
那
那一些變數
那一些變數的值
它可能是
對
就是自然
real number
那這邊呢
它就更
說
限定它的
就是
只有
0和1
所以呢
對
這個地方
是要跟同學講說
如果你要去驗證說
欸
ttt 這個組合
到底是不是 true
對
有一種方法是什麼
就是把 stack 2
就是第二張的 stack
那個 path
就是 expression
evaluation
把它
用進來這樣
要用兩次
就是
這是 stack
要兩次的
兩個 face
那第一個 face 在幹嘛
老師啊
第一個 face 在幹嘛
蛤
對
你們回去讀書
第一個 face 不是就是
假設它是一個 in order 的順序
是一個 expression
第一個 face 在幹嘛
第一個 face 要把它變成什麼
post order 的 expression
好
這叫第一個 face 這樣
這是 post order 的 expression 這樣
那第二個 face 要幹嘛
第二個 face 就是
根據你這個 post order 的 expression
那
我要去預估它的值這樣
那第二個 face 的話
其實還蠻簡單的
就是反正你看到數字
數字啊
就是就把它放到 stack 裡面
看到 operator
加減乘除
就把它
從 stack 裡面
最上面的兩個 node
把它抓出來
去做完 operation
再放到 stack 裡面這樣
那就叫 face 2 這樣
所以
欸
事實上
對
這個要去測試
這個
是否是 true
是可以用到 stack 裡面的
把它轉成 post order
好
那接下來呢
再根據 post order
就是利用另外一個 stack
來決定這樣
對
那我們就不用講了這樣
但事實上
我們還有一個更快的方法
就是我們可以把它變成一個 tree
對
然後 tree
做完這些事情以後
你要做什麼事
我就直接針對這個 tree
去做 post order
做完 post order 以後呢
在 tree traverse 的過程之中
我就去 evaluate 它
所以整個 tree
做完 post order
traversal 以後
答案就出來了這樣
就只有一個 face 而已
就是隻有一個 face 而已
那當然你就說
老師那還要建一個 tree 啊
就是
這檔案就是沒辦法
避掉這樣
那所以呢
如果要做到這樣子的事情
就是不是唯一的解
下面所講的不是唯一的解
因為在上面那個 slide
我已經跟大家講過了
你可以用到 chop 的 tool
是 stack 那個地方
的方法去解這個這樣
那大家來看一下
另外一種解法是什麼呢
就是去透過 tree traversal 這樣
用 post order 這樣
那為了要達到
這樣子的目的的話
就是這個 tree
要經過設計過這樣
那它的設計的準則是什麼
就是它有四個欄位
四個欄位
那這四個欄位分別是
left child 就指向
左邊的 child 這樣
data 就它自己本身
data 就是說
它現在 x y
如果等於 true 的話
這個 data 就是 1 這樣
然後 value 是什麼
value 等一下會講
就是它會對
它的左邊或右邊的指數
做完 operation
結果會放在哪裡
就是放結果 result
會放在 value 裡面
那 right child 的話
它指向它的右邊指數這樣
所以總共會有四個欄位
其實原來的 tree
就只有三個欄位
自己的 left right
還有它自己的 data
但是在這地方
要多一個欄位叫 value
它會去做 evaluation
值就會放到 value 裡面
所以這個是
第一個版本
這是演算法
那演算法是什麼呢
很簡單
假設我有 n 個 parameter
那我去產生 2n 種組合
對每一種組合
去 traverse 那棵 tree
然後看它最後的結果
evaluate 這個結果
那如果它是真的話
就是把它這種組合
把它 output 出來
那所以大家看一下
像剛剛有八種組合
八種組合
就是像剛剛說的
Full loop
那如果你是
會讓這個式子變成 true 的話
你要把這個組合
output 出來
然後說
它是會讓它變成 true 這樣
所以這個演算法
就很簡單
你知道怎麼寫嗎
還不知道
那現在我們進入到
它到底怎麼寫
寫法就這麼簡單
那你看
之前那個 stack
第二章 chapter
用了老半天
怎麼這麼簡單
那這個的話
就是一個 post-order evaluate
procedure
就叫 post-order evaluate
那它問進去的參數
就是 root
就是 tree
那接下來大家看一下
這 post-order evaluate
它會做什麼事
傳進去給它一個參數
就是要 x
那先去判斷這個 x
是否是空的
那如果是空的
那就跳脫出來吧
你根本連做都不用做
那如果不是空的話
那做下面的事情
那注意一下
我們已經跟你講了
是要去做 post-order
post-order 是什麼
lrv
如果有左邊
就先把你放左邊
如果有右邊
就把你放右邊
然後不行的話
lrv 都走過了
那就是做什麼事
就是 visit
所以 post-order
依照 post-order
先往左邊走
先往右邊走
先往左邊走
接下來往右邊走
那接下來這三
這個指航指令很重要
其實也不重要
其實它很簡單
那它在做什麼事情
首先去判斷這個 data
x 的 data
假設我們就往左邊走
也往右邊走
就一直走到最下面
最下面的 node
那我們就看一下它的 data
那這 data 有幾種 case
幾種 case 是什麼
它是 not
這個 data 是 not
那第二個 data 是 n
因為它可能是 operator
是 n
那第三個可能是 or
那假設它是參數
假設它是 assignment
它可能會是 true
logic true 或 logic false
logic true 就是說
它不是 operator
它就是那個參數
那這個參數假設我設成 true 的話
它的 value 就變成 true
那設成 false 的話
它的 value 就變成 false
那接下來大家看一下
這邊在做什麼事
假設是 not 的話
它做什麼事
它做的事情就是
把它的 right child 的 value
把它 x 所指的 right 右邊
的那個 node
那個 node 的 value 值
把它設成 not
那結果呢
就給它等於 x 的 value 這樣
那假設要做 n 了呢
其實假設你有一個 node
它有 left 和 right 這兩個 node
它要去做 n 了呢
那很簡單
就是 left child 的值和 right child 的值
去做一個 n 的動作
然後把結果丟到 value 去
就是 x 的 value 去
那 or 呢
就是把它左邊和右邊的指數
去做一個 or 的動作
放到 value 這樣
所以很重要就是說
data
這個當然為什麼要有四個欄位
left child right child
data
data 它可能是 operator
它可能也是那些 variable
變數
那 value 放的是什麼
就是左邊和右邊指數
他們 data 去做 operation 這樣
去做一些 operation 這樣
做完 operation 呢
就是資料就放到
他的 parent child 的 value 去
parent child 的 value 去
所以這一長串呢
就是透過 post order
最後的結果
你猜這個最後的結果
會在哪裡
它最後的結果
是放在 root 的 value 裡面
是 along rv 嘛
對 post order
最後 output 出來的東西是什麼
root 的 value 這樣
做完下面
你就可以想像一下
它是做什麼
對
它就會是
比方說
這個 x1 是 true
這個 x2 是 false 這樣
那它做的事情是什麼
比方說
它走到這邊
走不下去了這樣
那 x1 是 true 嘛
它就會設成
x1 就是 1 了這樣
那接下來呢
它就開始去
對 就是去往它的上面走這樣
那要把 x2 設成
x2 假設是 true
然後 not x2 就是
false 這樣
那 true and false
結果是什麼
false 這樣
那這個就
依照這樣子的準則
它 recursive
去對待它
去做 evaluation 這樣
最後結果會放在
root 的 value 這樣
那假設 root 的 value 是 true 的話
x1 x2 x3
的 combination 印出來的
所以請同學回去再看一下
這個
這個程式這樣
請同學回去再去看一下
看一下這個程式
那同樣的
這個程式
是可以被應用到
第二章
的那個
expression 的 evaluation 這樣
那請同學想想看
如果要用到那邊去
做 evaluation expression 的話
這個程式要怎麼改
這程式要怎麼改
那我們今天上到這裡
