接上回樹結構

二叉樹是一個程序，總不能是我們人為的去說吧，所以我們要用專門的程序來對二叉樹進行遍歷，并用程序來表達，讓我們每一個元素去用電腦來運用，這就是我們今天要說的主題——二叉樹的遍歷

這里呢我們舉了3個結點的遍歷方法，分別為先序，中序和后序

通過這些遍歷方法我們可以把擁有3個結點的數(shù)遍歷出來，至于比較大的樹，我們可以把他拆成很多3個結點的小樹，再用上面的方法遍歷出來。

先序遍歷

這里呢我們先學習先序遍歷

我們以一顆九個結點的二叉樹來進行講解

先遍歷根節(jié)點，再遍歷左子樹。即：1是根節(jié)點先遍歷1,1的左子樹是2,4,5,7，而4又是2的左子樹，所以遍歷4，最后再遍歷4的左子樹，7，則這部分答案為1,2,4,7

遍歷完左子樹就到右子樹了，而4沒有右子樹，所以直接來到2，2的右子樹是5，遍歷5

則這部分結果為5

遍歷完1的左子樹以后就應該到右子樹了，即3,6,8,9，而3,6,8,9里面3是這課樹的根節(jié)點，所以遍歷3,3沒有左子樹，所以遍歷右子樹即6，而6的左子樹是8，所以遍歷8

則這部分答案為3,6,8

最后遍歷右子樹，9

最后呢我們的答案是124753689.

正如上面的知識點所說，先序遍歷有3個原則：

1.先訪問根結點；

2.先序遍歷左子樹；

3.先序遍歷右子樹。

其實遍歷就可以總結為3個字“根，左，右”（根節(jié)點，左子樹，右子樹）

通過上面的講解也可以很清晰的看出來了

鞏固一下，我們再來做一道題

用先序遍歷以下的樹。

做做試試

答案是：1，2，4，5，8，9，3，6，7，10

你做對了嗎？

中序遍歷

學完了先序，我們再來看中序

圖都一樣，我們挨個看看

中序的遍歷方法就有點逆向了，大家看看

圖一：我們先遍歷左子樹（最左最下的（注意是先最左在最下）），是7，而7又是4的左子樹，左子樹遍歷完了，就應該遍歷根節(jié)點了，所以下一個為4,。根節(jié)點以后就應該是右子樹，但是我們發(fā)現(xiàn)這里的4沒有右子樹，所以我們直接跳過。來看到4,4又是2的左子樹所以我們下一個應該遍歷的是根節(jié)點即2.所以第一部分的結果為7,4,2

圖二：接上面，左子樹，根節(jié)點都遍歷完了，就應該到右子樹了，右子樹只有5，所以我們直接輸出5就行，所以接著就是7,4,2,5

圖3：一樣的，我們發(fā)現(xiàn)1的左子樹遍歷完了，接下來就是根節(jié)點，1所以目前是7,4,2,5,1

圖4：接下來就應該遍歷有右子樹了，而這里右子樹的根節(jié)點3沒有左子樹，那么久遍歷根節(jié)點即3，所以接下來就是7,4,2,5,1,3

圖5:3遍歷完左子樹和根節(jié)點就到了右子樹，即6，而6作為8,9的根節(jié)點那就應該先遍歷左子樹即8，接下來就是根節(jié)點6，左后是左孩子9，所以最后結果是7,4,2,5,1,3,8,6,9

我們也是遵守了以下的3個規(guī)律：

1.中序遍歷左子樹；

2.訪問根結點；

3.中序遍歷右子樹。

總結起來就是“左，根，右”（左子樹，根節(jié)點，右子樹）

這個中序是很難的，經(jīng)常會考，大家需要牢記。

我們在做1道題鞏固一下吧：

還是之前那副圖。大家做一下

答案是：4,2，8,5,9,1,6,3,10,7

怎么樣，做對了么？沒做對那就再看一遍吧（這道題挺難的）

后序遍歷

看圖

根據(jù)后序遍歷的規(guī)則，我們先遍歷左子樹再遍歷右子樹，而這課大樹的根節(jié)點為1，而1的左子樹是2，而2的左子樹又是4，以此類推，則最后一個左孩子是7，而隸屬于7這個小樹沒有右子樹所以直接遍歷根節(jié)點，4，最后2這個根節(jié)點的左子樹遍歷完了就應該到右子樹，則遍歷出5，最后遍歷根節(jié)點2.所以這個部分的答案是，7,4,5,2

遍歷完左邊就應該到右邊了即3,6,8,9，像之前一樣，先遍歷左子樹，而3沒有左子樹所以直接遍歷右子樹6，而6的左子樹是8，遍歷8，接下來就是右子樹9，遍歷9，遍歷根節(jié)點6，最后遍歷1的右子樹這個樹的根節(jié)點，3，則這部分的結果是，8,9,6,3

最后遍歷根節(jié)點1.。所以答案如下

7,4，5,2,8,9,6,3,1.

所以

后（根）序遍歷規(guī)則如下：

1.后序遍歷左子樹；

2.后序遍歷右子樹；

3,。訪問根結點。

做題。

思考

答案是：4,2，8，5，9，1，6，3，10，7

現(xiàn)在我們已經(jīng)學會了樹的3種基本遍歷方法

接著努力吧

下一節(jié)課我們來說關于樹建立的代碼

灰常重要，記得來看

點個贊吧，謝謝你們！