演算法實作範例!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沒有右子樹,所以執行結束。

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

執行結果

 

想閱讀更多請點我

熱門文章
娛樂報報/阿翔父親節帶全家出遊 見10歲女兒穿短裙...跟老婆抱怨:拿去丟了
娛樂報報/阿翔父親節帶全家出遊 見10歲女兒穿短裙...跟老婆抱怨:拿去丟了

CTWANT

憂鬱症到底會不會好?百萬YouTuber阿滴罹病過程:焦慮、恐慌、憂鬱狂暴襲來
憂鬱症到底會不會好?百萬YouTuber阿滴罹病過程:焦慮、恐慌、憂鬱狂暴襲來

圓神出版

艾成墜樓身亡! 憂鬱症是自殺警訊? 身邊親友出現「3大跡象」要警覺
艾成墜樓身亡! 憂鬱症是自殺警訊? 身邊親友出現「3大跡象」要警覺

潮健康

攝影師「殯儀館搭訕正妹」⋯一看IG臉綠了 「車上突飄怪味」慘出車禍
攝影師「殯儀館搭訕正妹」⋯一看IG臉綠了 「車上突飄怪味」慘出車禍

CTWANT

台南亂葬崗「拍出事」 靈異節目主持人被鬼王附身命理師下跪求情 
台南亂葬崗「拍出事」 靈異節目主持人被鬼王附身命理師下跪求情 

CTWANT

艾成墜樓亡/曾曝中邪「背唐詩、暴食、自殘、裸體欲跳樓」 崩潰認:有聲音叫我跳
艾成墜樓亡/曾曝中邪「背唐詩、暴食、自殘、裸體欲跳樓」 崩潰認:有聲音叫我跳

CTWANT

悚!柬埔寨正妹站一排喊「天堂」 誘豬仔屠宰酷刑畫面曝
悚!柬埔寨正妹站一排喊「天堂」 誘豬仔屠宰酷刑畫面曝

SETN三立新聞網

慈濟出手!赴柬救出2台人 網曝「2點」讚翻:世界級的強
慈濟出手!赴柬救出2台人 網曝「2點」讚翻:世界級的強

SETN三立新聞網

台積電上班2週突離職!新人赴柬想發財 他驚:已經失聯了
台積電上班2週突離職!新人赴柬想發財 他驚:已經失聯了

SETN三立新聞網

排便習慣改變且腹瀉、血便 醫:及早就醫檢查可能是腸道癌症警訊!
排便習慣改變且腹瀉、血便 醫:及早就醫檢查可能是腸道癌症警訊!

爽爆新聞網

「豬仔」想回家詐騙集團冷血回「2條路」 親友聽完心都涼了
「豬仔」想回家詐騙集團冷血回「2條路」 親友聽完心都涼了

中廣新聞

【自我診斷】罹患憂鬱症和成癮症的機率有多少?你的多巴胺足夠嗎? 如何提升引領快樂生活?
【自我診斷】罹患憂鬱症和成癮症的機率有多少?你的多巴胺足夠嗎? 如何提升引領快樂生活?

商周出版

她長期鼻塞好不了  檢查發現「癌細胞」長滿鼻腔!  醫:鼻咽癌「4徵兆」別輕忽
她長期鼻塞好不了 檢查發現「癌細胞」長滿鼻腔! 醫:鼻咽癌「4徵兆」別輕忽

潮健康

八里男經商失敗無力下葬老母冰箱塞屍5年 男子:都有固定祭拜
八里男經商失敗無力下葬老母冰箱塞屍5年 男子:都有固定祭拜

CTWANT

阿里山英迪格酒店年底亮相!觀星平台坐擁絕美雲海與滿天銀河 全日餐廳享「鄒族」原民特色料理
阿里山英迪格酒店年底亮相!觀星平台坐擁絕美雲海與滿天銀河 全日餐廳享「鄒族」原民特色料理

上報Up Media

百萬網紅被羊駝麥可圈粉!王宥忻分享「萌獸樂園NFT」完銷秘訣
百萬網紅被羊駝麥可圈粉!王宥忻分享「萌獸樂園NFT」完銷秘訣

LIFE生活網小編

全台唯一機車得來速?夜市買香酥雞 大排長龍免下車
全台唯一機車得來速?夜市買香酥雞 大排長龍免下車

TVBS新聞網

麥當勞買一送一!韓式炸雞新口味「蜂蜜洋釀」登場、「網友最愛 TOP 5 套餐」大公開
麥當勞買一送一!韓式炸雞新口味「蜂蜜洋釀」登場、「網友最愛 TOP 5 套餐」大公開

上報Up Media

男子將老母遺體放冰箱父女伴屍達5年 女童曝:阿嬤在冰箱不出來!
男子將老母遺體放冰箱父女伴屍達5年 女童曝:阿嬤在冰箱不出來!

CTWANT

超血腥!柬埔寨活摘器官畫面瘋傳 原始影片可能來自這國
超血腥!柬埔寨活摘器官畫面瘋傳 原始影片可能來自這國

上報Up Media

烤網怎麼會有鋼絲! 燒烤店用餐 夾到4條鋼絲
烤網怎麼會有鋼絲! 燒烤店用餐 夾到4條鋼絲

TVBS新聞網

基隆社區地下室爆炸起火 3警消打火遭濃煙嗆傷、1人被抬出
基隆社區地下室爆炸起火 3警消打火遭濃煙嗆傷、1人被抬出

CTWANT

將愛傳出去 永慶加盟四品牌桃竹苗區號召民眾挽袖捐血
將愛傳出去 永慶加盟四品牌桃竹苗區號召民眾挽袖捐血

匯流新聞網CNEWS

不只柬埔寨!全球反詐騙組織點名「這5國家」:不要去就對了
不只柬埔寨!全球反詐騙組織點名「這5國家」:不要去就對了

民視新聞

尪是泰柬人蛇首腦! 他曝「女星3特徵」…揭9成被賣台人下場
尪是泰柬人蛇首腦! 他曝「女星3特徵」…揭9成被賣台人下場

CTWANT

印度瑜珈冠軍:3分鐘「寶特瓶瑜珈術」不只瘦手臂,還能改善肩頸僵硬
印度瑜珈冠軍:3分鐘「寶特瓶瑜珈術」不只瘦手臂,還能改善肩頸僵硬

良醫健康網

暑假必看耍廢互動展「有問題的!展!?覽???」
暑假必看耍廢互動展「有問題的!展!?覽???」

News586

台中6旬男坐工廠馬桶屍僵亡 兒子一開門嚇傻!檢警追查死因
台中6旬男坐工廠馬桶屍僵亡 兒子一開門嚇傻!檢警追查死因

CTWANT

到台中拍波波草!中社花市「波波球」可愛爆紅 打卡順拍紫色鼠尾草、賞鮮豔向日葵
到台中拍波波草!中社花市「波波球」可愛爆紅 打卡順拍紫色鼠尾草、賞鮮豔向日葵

上報Up Media

青春一夏!穿學生制服遊六福村 平日209元優惠價爽玩一整天
青春一夏!穿學生制服遊六福村 平日209元優惠價爽玩一整天

桃園電子報新聞網

50
0
分享