資訊專欄INFORMATION COLUMN
摘要：題目前序遍歷中序遍歷后序遍歷這些遍歷就是根據遍歷根節點的順序而定義的，前序遍歷就是優先遍歷根節點然后遍歷左右子節點，當然左右子節點也是根據這個原則遍歷的，那么中后序遍歷也一樣。
為什么會寫這篇文章
學習的時間越來越長總會忘掉一些東西，就比如向量，矩陣，二叉樹，鄰接表，太多太多東西，不用就都給忘了，今天看了這樣一道面試題：總結下來就是根據二叉樹的前中序遍歷，然后寫出后序遍歷，清晰的記得當時學習二叉樹的時候做這種題是很快的，可是我還真就卡住了，不是說需要做一會兒，是做不出來，看過好多遍使用程序實現DFS(深度優先)BFS(廣度優先)的例子，可是讓我用筆推斷，我還真就腦子瓦特了，所以也記錄一下，順便幫一下也忘記了手工推斷的你們回憶一下，你們一定都比我優秀，perfect。
題目：
前序遍歷
A D C E F G H B
中序遍歷
C D F E G H A B
后序遍歷？
這些遍歷就是根據遍歷根節點的順序而定義的，前序遍歷就是優先遍歷根節點然后遍歷左右子節點，當然左右子節點也是根據這個原則遍歷的，那么中后序遍歷也一樣。那么我們應該怎么去做呢？其實就是根據前中遍歷的結果推斷出這顆樹。。。
第一步
根據前序遍歷原則找出根節點：A 因為優先遍歷根節點
根據根節點A和中序遍歷劃分前中序遍歷的左右子樹，以中左表示，前序遍歷的左右子樹，以前左表示：
中左：C D F E G H
中右：B
前左：D C E F G H
前右：B
第二步
根據上面的中左，前左繼續劃分根節點：D 由于右子樹就一個節點，所以就結束了
根據根節點D和中序遍歷劃分前中序遍歷的左右子樹
中左：C
中右：F E G H
前左：C
前右：E F G H
第三步
根據上面的中右，前右繼續劃分根節點：E 由于左子樹就一個節點，所以就結束了
根據根節點E和中序遍歷劃分前中序遍歷的左右子樹
中左：F
中右：G H
前左：F
前右：G H
第四步
根據上面的中右，前右繼續劃分根節點：G 由于左子樹就一個節點，所以就結束了
根據根節點G和中序遍歷劃分前中序遍歷的左右子樹
中左：
中右：H
前左：
前右：H
終于構建出來這顆樹了，接下來根據后序遍歷原則去寫：
后序遍歷結果亮相：
C F H G E D B A
只有多學習才能變得更強，還是那句話:
堅持一件事，對自己。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43481.html
摘要：像剛才的這幅圖，就是二叉搜索樹。而我們本文要學習的內容，就是如何寫一個二叉搜索樹。但在二叉搜索樹中，我們把節點成為鍵，這是術語。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學習學習數據結構與算法四二叉搜索樹 本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據...
摘要：代碼實現如下二叉樹的創建與銷毀二叉樹的創建問題通過前序遍歷的數組給定一串字符串，代表的是空樹，其他的都是節點。 ??本篇博客我要來和大家一起聊一聊數據結構中的二...
摘要：當集合為空時，稱該二叉樹為空二叉樹。也就是說，如果一個二叉樹的層數為，且結點總數是，則它就是滿二叉樹。完全二叉樹完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。 ...
閱讀 4001·2023-04-26 02:13
閱讀 2244·2021-11-08 13:13
閱讀 2729·2021-10-11 10:59
閱讀 1732·2021-09-03 00:23
閱讀 1301·2019-08-30 15:53
閱讀 2275·2019-08-28 18:22
閱讀 3050·2019-08-26 10:45
閱讀 727·2019-08-23 17:58
