首先說明，這只是我個人的一些理解與體會，我寫下來是想讓自己能隨時隨地復(fù)習(xí)與思考，并不是說想去教人家，所以其中可能會有些我個人理解不對的地方，這也正是我寫博客的原因，這樣才能不斷進步，當(dāng)然如果對讀者有用的話，一起共勉。

?

今天我想記的是二叉樹的遍歷（先中后三種）。

我們都知道二叉樹的遍歷有四種，分別是先序遍歷（也叫前序遍歷），中序遍歷，后序遍歷以及層序遍歷，在這里我不講層序遍歷（層序遍歷是分別都從從每一層的左邊向右邊遍歷）。以下的圖是我自己畫的，將就點看就行。

? ? ? ? ? ? ? ? ? ??

?

? ?

我們都知道二叉樹分為根節(jié)點，左孩子，右孩子三部分，所以所謂先序中序后序遍歷，其實也就是訪問根節(jié)點的順序，首先，先序遍歷，即為訪問根節(jié)點->訪問左孩子->訪問右孩子。?其次，中序遍歷，即為訪問左孩子->訪問根節(jié)點->訪問右孩子。最后，以此類推，后序遍歷就是訪問右孩子->訪問左孩子->訪問根節(jié)點。

?

然后有一點，這樣不斷的訪問，縮小范圍，實質(zhì)上也是一個遞歸的過程，一個表面上的遞歸過程。在我的理解中，遞歸，就是不斷不斷的縮小同種類型的范圍，當(dāng)?shù)竭_某個點后，就開始不斷往回走，這在二叉樹的遍歷中就能表現(xiàn)出來，本身二叉樹遍歷的代碼就是一個遞歸的過程。

?

先序遍歷：訪問根節(jié)點->訪問左孩子->訪問右孩子。

如上圖，我們按照順序來，先訪問根節(jié)點，毫無疑問，先是A，然后訪問A的左孩子，然后，遞歸的形象化就出來了。因為A的左孩子又是一顆二叉樹，如上面所說，縮小范圍，所以，BCD就是一顆“新”二叉樹，我們繼續(xù)訪問根節(jié)點，為B，然后訪問左孩子，B的左孩子是C，其實，C也是一顆樹，只不過它是一顆左右孩子都為空的樹，繼續(xù)訪問根節(jié)點，為C。你看，對于BCD這棵樹（以下二叉樹我都簡稱為樹）而言，根->B，左孩子->C，右孩子->D，所以它就訪問結(jié)束了。然而，當(dāng)BCD樹訪問完了，對于整個樹來說，即A的左孩子，也訪問完了，所以又像上面說的“往回走”。所以接下來輪到訪問A的右孩子，對于E，為“新樹EF”的根節(jié)點，訪問，為E，E的左孩子為空，然后到右孩子，為F，F的左右都為空，至此，A的右孩子訪問結(jié)束，所以，對于此樹，先序遍歷的結(jié)果為ABCDEF?。

?

中序遍歷：訪問左孩子->訪問根節(jié)點->訪問右孩子。

中序遍歷也是如此的道理，先是訪問左孩子，左孩子還有左孩子，遞歸下去，訪問，為C，然后到根節(jié)點，為B，再到右孩子，為D，然后，對于整棵樹而言，左孩子訪問結(jié)束，輪到根節(jié)點，為A，然后，右孩子，對于“EF樹”來說，左孩子為空，根節(jié)點為E，右孩子為F，所以分別是為E，為F，至此，整棵樹的右孩子也訪問結(jié)束。所以，對于此樹，中序遍歷的結(jié)果為CBDAEF。

?

后序遍歷：訪問左孩子->訪問右孩子?->訪問根節(jié)點。

相信經(jīng)過前兩個的說明，大家也能掌握后序遍歷的情況了，我們直接來，左孩子，“BCD”，繼續(xù)左孩子，為C，右孩子，為D，根節(jié)點，為B，再到整棵樹的右孩子“EF”，左孩子，為空，右孩子，為F，根節(jié)點，為E，左右結(jié)束，根節(jié)點，為A。對于此樹，中序遍歷的結(jié)果為CDBFEA。

?

所以三種遍歷方式就是這樣，因為我畫的樹比較小，所以遞歸的效果不是很明顯的看出來，大家可以試著畫棵大點的樹，不斷縮小縮小，然后又層層返回，就能形象的理解遞歸了。

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/yellowgg/p/6735293.html

總結(jié)

以上是生活随笔為你收集整理的详细易懂的二叉树遍历（先中后）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。