演算法實作範例!LeetCode Solutions工程師必學:遍歷二元樹使用中序(inorder)列印

演算法實作範例!LeetCode Solutions工程師必學:遍歷二元樹使用中序(inorder)列印

深智數位資訊講堂 2021-07-09 15:16

LeetCode Solutions工程師必學:遍歷二元樹使用中序(inorder)列印

在這篇文章中,說明二元樹這個資料結構的概念,它在計算機科學中非常重要,有很多演算法都一定會運用到這種資料結構,也是初入職場工程師必刷的leetcode考題。

    假設有一顆二元樹如下:

    所謂中序列印是從左子樹往下走,直到無法前進就處理此節點,接著處理此節點的父節點,然後往右子樹走,如果右子樹無法前進則回到上一層。也可以用另一種解釋,遍歷左子樹(Left,縮寫是L)、根節點(Root,縮寫是D)、遍歷右子樹(Right,縮寫是R),整個遍歷過程簡稱是LDR

    用這個觀念遍歷上述二元樹可以得到下列結果:

    5, 9, 10, 13, 21, 28

    上述中序列印相當於可以得到由小到大的排序結果,如上所示,設計中序列印的遞迴函數步驟如下:

    1:如果左子樹節點存在,則遞迴呼叫self.left.inorder( ),往左子樹走。

    2:處理此節點(會執行此行,是因為左子樹已經不存在)。

    3:如果右子樹節點存在,則遞迴呼叫self.right.inorder( ),往右子樹走。

程式實例ch6_4.py:使用10, 21, 5, 9, 13, 28系列數字建立一個二元樹,然後使用中序方式列印。

 

執行結果

下列二元樹節點左邊的數字是中序遍歷列出節點值的順序。

 

為了方便解說,將節點改為英文字母,然後使用二元樹堆疊分析整個第25-31行遞迴inorder( )函數遍歷過程:

 1:由A進入inorder( )。

2:因為A的左子樹B存在,所以進入B的遞迴inorder( )。

3:B沒有左子樹,所以if B.left … 執行結束,圖形如下:

4:執行print B。

5:因為B的右子樹D存在,所以進入D的遞迴inorder( )。

 6:由於D沒有左子樹,所以if D.left … 執行結束,執行print D。

7:D沒有右子樹,所以if D.right … 執行結束,接下來執行print A。

8:因為A的右子樹C存在,所以進入C的遞迴inorder( )。

 9:因為C的左子樹E存在,所以進入E的遞迴inorder( )。

 10:由於E沒有左子樹,所以if E.left … 執行結束,執行print E。

 11:E沒有右子樹,所以if E.right … 執行結束,接下來執行print C。

12:因為C的右子樹F存在,所以進入F的遞迴inorder( )。

13:由於F沒有左子樹,所以if F.left … 執行結束,執行print F。

14:由於F沒有右子樹,所以執行結束。

    上述節點旁的數值則是列印的順序。

執行結果

 

想閱讀更多請點我

熱門文章
炎亞綸也吃過寶林餐點!半年前「出現3症狀」質疑:是否長期有問題?
炎亞綸也吃過寶林餐點!半年前「出現3症狀」質疑:是否長期有問題?

SETN三立新聞網

別再騎了!台南「這段」是腳踏車道 1個月取締機車高達265件
別再騎了!台南「這段」是腳踏車道 1個月取締機車高達265件

記者爆料網

3行人悠哉過馬路…救護車「被迫停讓15秒」阻礙救援 網怒轟:羞恥心在哪裡
3行人悠哉過馬路…救護車「被迫停讓15秒」阻礙救援 網怒轟:羞恥心在哪裡

CTWANT

寶林茶室「清庫存」害死人?台南女苦主曝巧合:遷店前剩4道菜可點
寶林茶室「清庫存」害死人?台南女苦主曝巧合:遷店前剩4道菜可點

中天新聞

快訊/記得帶傘!屏東大雨特報 雨彈狂炸到入夜
快訊/記得帶傘!屏東大雨特報 雨彈狂炸到入夜

中天新聞

全台變天!大雷雨「南往北狂炸」連下5天 午後1地雨勢最猛
全台變天!大雷雨「南往北狂炸」連下5天 午後1地雨勢最猛

TVBS新聞網

桃園男登山不慎滑落山坡成冰冷遺體 忠犬護屍4天3夜讓人動容
桃園男登山不慎滑落山坡成冰冷遺體 忠犬護屍4天3夜讓人動容

記者爆料網

台南公布第35波酒駕累犯名單 人數多達22人遍布14區
台南公布第35波酒駕累犯名單 人數多達22人遍布14區

記者爆料網

台灣才有!陸客狂讚「賣場1神級飲料」好喝到爆 沙士都輸了
台灣才有!陸客狂讚「賣場1神級飲料」好喝到爆 沙士都輸了

TVBS新聞網

致命元兇恐不只米酵菌酸!醫揭寶林案「救不了關鍵」:看亡者就知
致命元兇恐不只米酵菌酸!醫揭寶林案「救不了關鍵」:看亡者就知

TVBS新聞網

76歲雷洪重現經典「恰恰」爆橘拳 自曝天天靠「這一招」養生補腎
76歲雷洪重現經典「恰恰」爆橘拳 自曝天天靠「這一招」養生補腎

年代MUCH台

跟團旅遊比自由行棒!妹子試過一次就愛上:理智線不會斷裂
跟團旅遊比自由行棒!妹子試過一次就愛上:理智線不會斷裂

TVBS新聞網

見面會「門票滯銷」!主辦宣布李多慧高雄場取消 認:時間人力太困難
見面會「門票滯銷」!主辦宣布李多慧高雄場取消 認:時間人力太困難

中天新聞

寶林茶室粿條好毒!民眾不敢吃 醫師曝這2種食物更要注意
寶林茶室粿條好毒!民眾不敢吃 醫師曝這2種食物更要注意

CTWANT

快訊/「寶林茶室」禍首曝光!衛福部專家會議推測「這毒素」或成元兇
快訊/「寶林茶室」禍首曝光!衛福部專家會議推測「這毒素」或成元兇

中天新聞

寶林2死!台大醫喊避免「這種飯、麵」重複加熱 米酵菌酸更猛爆
寶林2死!台大醫喊避免「這種飯、麵」重複加熱 米酵菌酸更猛爆

TVBS新聞網

告五人演唱會宜蘭鄉親狂讚 幕後浩大工程紀錄全公開
告五人演唱會宜蘭鄉親狂讚 幕後浩大工程紀錄全公開

相信音樂

鴻海、廣達...黃仁勳欽點「8家將」護體輝達:AI是新的工業革命「台灣處於最中心位置」
鴻海、廣達...黃仁勳欽點「8家將」護體輝達:AI是新的工業革命「台灣處於最中心位置」

今周刊

50
0
分享