iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
Software Development

程式菜鳥自學C++資料結構演算法系列 第 14

[Day14]程式菜鳥自學C++資料結構演算法 – 二元樹的走訪Binary Tree Traversal

前言:昨天介紹完了二元樹的兩種儲存方式,今天要來介紹如何讀取二元樹,稱之為走訪,而走訪方式就有大約四種,今天就一一為大家介紹。

何謂走訪?走訪其實就是要讀取到每一個節點,不同的走訪方式在於要先處理哪一邊的資料,且左子樹的優先權必大於右子樹,所以重點就在根節點的位置在哪裡。

1.前序走訪 Preorder:

前序走訪的順序是根節點→左子樹→右子樹
https://ithelp.ithome.com.tw/upload/images/20210928/20140187ldWEt7qapv.png
牛刀小試:先把左子樹和右子樹想像成一個大節點,向上面的圖片一樣,會比較容易成功。
https://ithelp.ithome.com.tw/upload/images/20210928/20140187RShNXzi8i1.png
前序走訪:x+46-82

實作:這次用上一篇鏈結串列表示法的二元樹程式碼作範例,可以先準備好呦=U=
https://ithelp.ithome.com.tw/upload/images/20210928/20140187qwfEaTxgvL.png
https://ithelp.ithome.com.tw/upload/images/20210928/20140187MsNEXpYT2y.png

2.中序走訪 Inorder:

可以說是我們最熟悉的走訪方式,平常我們所寫的算式或是按計算機的順序都是中序走訪。中序走訪順序左子樹→根節點→右子樹
https://ithelp.ithome.com.tw/upload/images/20210928/20140187K3FX6kE7Gi.png
牛刀小試:
https://ithelp.ithome.com.tw/upload/images/20210928/2014018747sO3pvQuk.png
中序走訪:4+6x8-2

實作:
https://ithelp.ithome.com.tw/upload/images/20210928/20140187M2837Hn7gG.png
https://ithelp.ithome.com.tw/upload/images/20210928/20140187g5i4oCEWXb.png

3.後序走訪 Postorder:

後續走訪的順序左子樹→右子樹→根節點
https://ithelp.ithome.com.tw/upload/images/20210928/20140187Valot86UKY.png
牛刀小試:
https://ithelp.ithome.com.tw/upload/images/20210928/201401873pdBM4Iww8.png
後序走訪:46+82-x

實作:
https://ithelp.ithome.com.tw/upload/images/20210928/20140187oY6GRyFTP0.png

4.層序走訪 Level-order:

與前三種走訪方式較為不同,以層次的等級決定走訪的順序第一層→第二層→第三層…以此類推。

牛刀小試:
https://ithelp.ithome.com.tw/upload/images/20210928/20140187JIQtqdhUGC.png
層序走訪:x+-4682

實作:需用到佇列存取樹的節點。
https://ithelp.ithome.com.tw/upload/images/20210928/2014018727hzAdRxCo.png
https://ithelp.ithome.com.tw/upload/images/20210928/20140187OAT0fWirJr.png

今日小結:今天介紹了四種二元樹的走訪,只要注意根節點的位置就一定能輕鬆掌握,明天會把程式碼完整地補上還會繼續介紹二元樹的更多種運用。


上一篇
[Day13]程式菜鳥自學C++資料結構演算法 – 二元樹的儲存與實作
下一篇
[Day15]程式菜鳥自學C++資料結構演算法 – 二元樹的基本應用
系列文
程式菜鳥自學C++資料結構演算法30

尚未有邦友留言

立即登入留言