演算法 - 二叉樹的10種遍歷方法，你都會了么？( 一 )（遞歸遍歷的本質）

今天複習一下二叉樹的遍歷~

二叉樹的遍歷方式有很多，這篇文章講一下

遞歸的先序遍歷，中序遍歷，後序遍歷。

請仔細閱讀每個演算法的定義，定義讀懂了，程序自然就會寫了。

先給出二叉樹的節點定義。

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; }}

一、先序遍歷

遍歷根節點，如果根節點為空，返回；否則，遍歷根節點，然後先序遍歷左子樹，再先序遍歷右子樹。

public void preorderTraverse(TreeNode root){ System.out.println(root.val+" "); preorderTraverse(root.left); preorderTraverse(root.right);}

二、中序遍歷

路過根節點，如果根節點為空，返回；否則，中序遍歷左子樹，然後遍歷根節點，再中序遍歷右子樹。

public void inorderTraverse(TreeNode root){ inorderTraverse(root.left); System.out.println(root.val+" "); inorderTraverse(root.right);}

三、後序遍歷

路過根節點，如果根節點為空，返回；否則，後序遍歷左子樹，再後序遍歷右子樹，最後遍歷根節點。

public void postorderTraverse(TreeNode root){ postorderTraverse(root.left); postorderTraverse(root.right); System.out.println(root.val+" ");}

至此，我們可以發現一個問題。

為什麼三種遍歷方式在形式上如此一致？

解釋一下這個問題，就能更加深入的理解二叉樹遍歷問題。

我們嘗試把下圖這樣一棵二叉樹代入下面的程序：

public void traverse(TreeNode root){ if(root == null) return; //函數在這裡返回 //這裡被稱為經過 traverse(root.left); //在這裡函數暫停 traverse(root.right); return; //函數在這裡返回}

開始traverse(1);

經過1，開始traverse(2);

經過2，暫停traverse(2)，開始traverse(4);

經過4，暫停4，繼續4，traverse(4)返回；

繼續traverse(2)；

開始traverse(5);

經過5，暫停5，繼續5，traverse(5)返回；

traverse(2)返回；

繼續traverse(1)；

開始traverse(3);

經過3，暫停3，繼續3，traverse(3)返回。

traverse(1)返回。

跑完這段程序，我們會發現，

traverse函數是按照：1，2，4，5，3 的順序開始的，這正是先序遍歷的順序。

traverse函數是按照：4，5，2，3，1 的順序返回的，這正是後序遍歷的順序

那麼中序遍歷在哪裡呢？就是在」繼續「語句中，很容易發現。

其實，在函數的運行時棧中，函數的開始，」暫停「就是入棧操作，函數的」繼續「，返回就是出棧操作。

那麼我們就可以用」棧（Stack）「這種數據結構來模擬這種操作；思路再拓展一下，除了棧，我們還可以用其他數據結構來代替棧的功能，比如，二叉樹本身。

限於篇幅問題，這些將在下面的文章中講到。

在這篇文章中，我們通過二叉樹遍歷的遞歸定義寫出遞歸程序，然後通過思考函數的入棧，出棧順序，加深了對遞歸遍歷的理解。

李井瑞：演算法 - 二叉樹的遍歷( 二 )（非遞歸先序，中序，DFS先序，DFS後序）

下面是日常歡迎關注，歡迎點贊，歡迎評論，歡迎讚賞~~~歡迎歡迎~~

有看不懂的地方，歡迎評論留言喲~~~