在資料結構當中一個很重要的結構則是樹了，那么樹的先序，中序，后序遍歷是怎么進行起來的呢？
一.先序遍歷
先序遍歷是最簡單的，也就是使用深度優先搜索（DFS）演算法在樹當中進行遍歷，我們首先在樹的左端走到底，在往下走的時候，沒遇到一個節點就列印出來，直到走到底之后再向上回傳，如果遇到已經列印，也就是走過的節點則查看這個節點的右端有沒有沒有列印的節點，如有則列印，沒有則不列印，在下方這張圖當中數字代表我們列印節點的順序，1代表第一個就列印了出來，2代表第二個列印出來，
在上面這張圖當中，首先樹的根節點是“make money fast”，因此這個節點最先被列印出來，然后從左走到底，一次列印“motivation”，greed，這個時候走到底了，我們向上回傳，發現前一個節點motivition的右子節點還沒有列印，也就是avidity，因此列印出avidity作為第四個節點，第四個節點向下搜索發現沒有節點了，因此又向上回傳，直到樹的根節點，
發現樹的根節點下還有兩個子節點沒有列印，因此先列印這兩個子節點左邊的節點，也就是method，然后繼續往左下走，依次列印出stock fraud, ponzi scheme,bank robbery,最后向上回傳列印出最后一個節點References，這是這三個遍歷方法當中最簡單的一個方法了，接下來我們來看中序遍歷，
二.中序遍歷
如下圖所示：
中序遍歷是我們走到底之后發現沒有沒有東西了才開始列印，而不是像先序一樣邊走邊列印，在一棵子樹當中的列印順序是“左節點——跟節點——右節點”，因此我們也是首先向左下遍歷到最底部，發現1下面沒有東西了，因此向上回傳列印跟節點，也就是2，列印完之后再前往右節點進行搜索，進入右節點發現4還有子節點，因此先列印左邊的子節點3，再列印中間的4，最后大印5，接著向上回傳到6，這個是整個左子樹的根節點，因此將其列印，再遍歷右子樹即可，
三.后序遍歷
如下所示：
后序遍歷就是先列印最底部的東西，和先序列印相反，遵循先遍歷左樹，然后進行“左樹——右樹——中樹”的順序進行列印，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/2195.html
標籤：其他
上一篇：深入淺出二叉樹
下一篇：LeetCode-二叉樹