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