二叉樹遍歷

遍歷分類

遍歷二叉樹的思路有 4 種，分別是：

• 前序遍歷二叉樹，有遞歸和非遞歸兩種方式；
• 中序遍歷二叉樹，有遞歸和非遞歸兩種方式；
• 后序遍歷二叉樹，有遞歸和非遞歸兩種方式；
• 層次遍歷二叉樹

前序遍歷

流程描述

所謂前序遍歷二叉樹，指的是從根結(jié)點(diǎn)出發(fā)，按照以下步驟訪問二叉樹的每個(gè)結(jié)點(diǎn)：

1. 訪問當(dāng)前結(jié)點(diǎn)；
2. 進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；
3. 遍歷完當(dāng)前結(jié)點(diǎn)的左子樹后，再進(jìn)入它的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)；

舉個(gè)簡單的例子，下圖是一棵二叉樹：

前序遍歷這棵二叉樹的過程是：

訪問根節(jié)點(diǎn) 1；
進(jìn)入 1 的左子樹，執(zhí)行同樣的步驟：訪問結(jié)點(diǎn) 2；進(jìn)入 2 的左子樹，執(zhí)行同樣的步驟：訪問結(jié)點(diǎn) 4；結(jié)點(diǎn) 4 沒有左子樹；結(jié)點(diǎn) 4 沒有右子樹；進(jìn)入 2 的右子樹，執(zhí)行同樣的步驟：訪問結(jié)點(diǎn) 5；結(jié)點(diǎn) 5 沒有左子樹；結(jié)點(diǎn) 5 沒有右子樹；
進(jìn)入 1 的右子樹，執(zhí)行同樣的步驟：訪問結(jié)點(diǎn) 3；進(jìn)入 3 的左子樹，執(zhí)行同樣的步驟：訪問結(jié)點(diǎn) 6；結(jié)點(diǎn) 6 沒有左子樹；結(jié)點(diǎn) 6 沒有右子樹；進(jìn)入 3 的右子樹，執(zhí)行同樣的步驟：訪問結(jié)點(diǎn) 7；結(jié)點(diǎn) 7 沒有左子樹；結(jié)點(diǎn) 7 沒有右子樹； 

經(jīng)過以上過程，就訪問了二叉樹中的各個(gè)結(jié)點(diǎn)，訪問的次序是：

1 2 4 5 3 6 7

代碼實(shí)現(xiàn)

/*** 前序遍歷- 遞歸實(shí)現(xiàn)* 訪問當(dāng)前結(jié)點(diǎn)；* 進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；* 遍歷完當(dāng)前結(jié)點(diǎn)的左子樹后，再進(jìn)入它的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)；* @param treeNode*/public static void preTraverseForRecursion(TreeNode treeNode){if (treeNode != null){// 訪問當(dāng)前節(jié)點(diǎn)printTreeNode(treeNode);// 訪問當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)preTraverseForRecursion(treeNode.left);// 訪問當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)preTraverseForRecursion(treeNode.right);}}/*** 前序遍歷- 非遞歸實(shí)現(xiàn)* 眾所周知：遞歸實(shí)現(xiàn)無非是使用了棧結(jié)構(gòu)來實(shí)現(xiàn)的，壓棧，出棧，所以非是遞歸實(shí)現(xiàn)前序遍歷就是自己實(shí)現(xiàn)棧* 訪問當(dāng)前結(jié)點(diǎn)；* 進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；* 遍歷完當(dāng)前結(jié)點(diǎn)的左子樹后，再進(jìn)入它的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)；* @param treeNode*/public static void preTraverseForNoRecursion(TreeNode treeNode){TreeNode curr = treeNode;TreeNodeStack stack = new TreeNodeStack();while (curr != null || !stack.isEmpty()){if (curr != null){// 訪問當(dāng)前節(jié)點(diǎn)printTreeNode(curr);stack.push(curr);curr = curr.left;}else {TreeNode pop = stack.pop();curr = pop.right;}}}

/*** 樹節(jié)點(diǎn)棧*/
@Data
public class TreeNodeStack {private int top = -1;private TreeNode[] stack = new TreeNode[10];public boolean isEmpty(){return top < 0;}/*** 入棧* @param treeNode*/public void push(TreeNode treeNode){top++;stack[top] = treeNode;}/*** 出棧* @return*/public TreeNode pop(){if (top < 0){return null;}TreeNode treeNode = stack[top];top--;return treeNode;}
}

中序遍歷

流程描述

二叉樹的中序遍歷，指的是從根結(jié)點(diǎn)出發(fā)，按照以下步驟訪問二叉樹中的每個(gè)結(jié)點(diǎn)：

1. 先進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；
2. 訪問當(dāng)前結(jié)點(diǎn)；
3. 最后進(jìn)入當(dāng)前結(jié)點(diǎn)的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)。

中序遍歷這棵二叉樹的過程是：

進(jìn)入結(jié)點(diǎn) 1 的左子樹，訪問左子樹中的結(jié)點(diǎn)；進(jìn)入結(jié)點(diǎn) 2 的左子樹，訪問左子樹中的結(jié)點(diǎn)；試圖進(jìn)入結(jié)點(diǎn) 4 的左子樹，但該結(jié)點(diǎn)沒有左子樹；訪問結(jié)點(diǎn) 4；試圖進(jìn)入結(jié)點(diǎn) 4 的右子樹，但該結(jié)點(diǎn)沒有右子樹；訪問結(jié)點(diǎn) 2；進(jìn)入結(jié)點(diǎn) 2 的右子樹，訪問右子樹中的結(jié)點(diǎn)；試圖進(jìn)入結(jié)點(diǎn) 5 的左子樹，但該結(jié)點(diǎn)沒有左子樹；訪問結(jié)點(diǎn) 5；試圖進(jìn)入結(jié)點(diǎn) 5 的右子樹，但該結(jié)點(diǎn)沒有右子樹；
訪問結(jié)點(diǎn) 1；
進(jìn)入結(jié)點(diǎn) 1 的右子樹，訪問右子樹中的結(jié)點(diǎn)；進(jìn)入結(jié)點(diǎn) 3 的左子樹，訪問左子樹中的結(jié)點(diǎn)；試圖進(jìn)入結(jié)點(diǎn) 6 的左子樹，但該結(jié)點(diǎn)沒有左子樹；訪問結(jié)點(diǎn) 6；試圖進(jìn)入結(jié)點(diǎn) 6 的右子樹，但該結(jié)點(diǎn)沒有右子樹；訪問結(jié)點(diǎn) 3；進(jìn)入結(jié)點(diǎn) 3 的右子樹，訪問右子樹中的結(jié)點(diǎn)；試圖進(jìn)入結(jié)點(diǎn) 7 的左子樹，但該結(jié)點(diǎn)沒有左子樹；訪問結(jié)點(diǎn) 7；試圖進(jìn)入結(jié)點(diǎn) 7 的右子樹，但該結(jié)點(diǎn)沒有右子樹；

最終，中序遍歷圖 1 中的二叉樹，訪問各個(gè)結(jié)點(diǎn)的順序是：

4 2 5 1 6 3 7

代碼實(shí)現(xiàn)

/*** 中序遍歷-遞歸實(shí)現(xiàn)* 二叉樹的中序遍歷，指的是從根結(jié)點(diǎn)出發(fā)，按照以下步驟訪問二叉樹中的每個(gè)結(jié)點(diǎn)：* 1. 先進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；* 2. 訪問當(dāng)前結(jié)點(diǎn)；* 3. 最后進(jìn)入當(dāng)前結(jié)點(diǎn)的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)。* @param treeNode*/public static void inTraverseForRecursion(TreeNode treeNode){if (treeNode != null){// 遞歸-當(dāng)問當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)inTraverseForRecursion(treeNode.left);// 訪問當(dāng)前節(jié)點(diǎn)printTreeNode(treeNode);// 遞歸-訪問當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)inTraverseForRecursion(treeNode.right);}}/*** 中序遍歷-非遞歸實(shí)現(xiàn)* 二叉樹的中序遍歷，指的是從根結(jié)點(diǎn)出發(fā)，按照以下步驟訪問二叉樹中的每個(gè)結(jié)點(diǎn)：* 1. 先進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；* 2. 訪問當(dāng)前結(jié)點(diǎn)；* 3. 最后進(jìn)入當(dāng)前結(jié)點(diǎn)的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)。* @param treeNode*/public static void inTraverseForNoRecursion(TreeNode treeNode){TreeNode curr = treeNode;TreeNodeStack stack = new TreeNodeStack();while (curr != null || !stack.isEmpty()){if (curr != null){// 入棧順序：1, 2, 4,stack.push(curr);curr = curr.left;}else {// 出棧順序：4， 2， 1TreeNode pop = stack.pop();printTreeNode(pop);// 然后訪問右節(jié)點(diǎn)curr = pop.right;}}}

后序遍歷

流程描述

后序遍歷二叉樹，指的是從根結(jié)點(diǎn)出發(fā)，按照以下步驟訪問樹中的每個(gè)結(jié)點(diǎn)：

1. 優(yōu)先進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；
2. 如果當(dāng)前結(jié)點(diǎn)沒有左子樹，則進(jìn)入它的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)；
3. 直到當(dāng)前結(jié)點(diǎn)的左子樹和右子樹都遍歷完后，才訪問該結(jié)點(diǎn)。

以下圖所示的二叉樹為例：

后序遍歷這棵二叉樹的過程是：

從根節(jié)點(diǎn) 1 出發(fā)，進(jìn)入該結(jié)點(diǎn)的左子樹；進(jìn)入結(jié)點(diǎn) 2 的左子樹，遍歷左子樹中的結(jié)點(diǎn)：進(jìn)入結(jié)點(diǎn) 4 的左子樹，但該結(jié)點(diǎn)沒有左孩子；進(jìn)入結(jié)點(diǎn) 4 的右子樹，但該結(jié)點(diǎn)沒有右子樹；訪問結(jié)點(diǎn) 4；進(jìn)入結(jié)點(diǎn) 2 的右子樹，遍歷右子樹中的結(jié)點(diǎn)：進(jìn)入結(jié)點(diǎn) 5 的左子樹，但該結(jié)點(diǎn)沒有左孩子；進(jìn)入結(jié)點(diǎn) 5 的右子樹，但該結(jié)點(diǎn)沒有右孩子；訪問結(jié)點(diǎn) 5；訪問結(jié)點(diǎn) 2；
進(jìn)入結(jié)點(diǎn) 1 的右子樹，遍歷右子樹中的結(jié)點(diǎn)：進(jìn)入結(jié)點(diǎn) 3 的左子樹，遍歷左子樹中的結(jié)點(diǎn)：進(jìn)入結(jié)點(diǎn) 6 的左子樹，但該結(jié)點(diǎn)沒有左孩子；進(jìn)入結(jié)點(diǎn) 6 的右子樹，但該結(jié)點(diǎn)沒有右子樹；訪問結(jié)點(diǎn) 6；進(jìn)入結(jié)點(diǎn) 3 的右子樹，遍歷右子樹中的結(jié)點(diǎn)：進(jìn)入結(jié)點(diǎn) 7 的左子樹，但該結(jié)點(diǎn)沒有左孩子；進(jìn)入結(jié)點(diǎn) 7 的右子樹，但該結(jié)點(diǎn)沒有右孩子；訪問結(jié)點(diǎn) 7；訪問結(jié)點(diǎn) 3；
訪問結(jié)點(diǎn) 1。

最終，后序遍歷圖 1 中的二叉樹，訪問各個(gè)結(jié)點(diǎn)的順序是：

4 5 2 6 7 3 1

代碼實(shí)現(xiàn)

 /*** 后序遍歷-遞歸實(shí)現(xiàn)* 后序遍歷二叉樹，指的是從根結(jié)點(diǎn)出發(fā)，按照以下步驟訪問樹中的每個(gè)結(jié)點(diǎn)：* 1. 優(yōu)先進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；* 2. 如果當(dāng)前結(jié)點(diǎn)沒有左子樹，則進(jìn)入它的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)；* 3. 直到當(dāng)前結(jié)點(diǎn)的左子樹和右子樹都遍歷完后，才訪問該結(jié)點(diǎn)。* @param treeNode*/public static void postTraverseForRecursion(TreeNode treeNode){if (treeNode != null){// 遞歸-當(dāng)問當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)postTraverseForRecursion(treeNode.left);// 遞歸-訪問當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)postTraverseForRecursion(treeNode.right);// 訪問當(dāng)前節(jié)點(diǎn)printTreeNode(treeNode);}}/*** 后序遍歷-非遞歸實(shí)現(xiàn)* 后序遍歷二叉樹，指的是從根結(jié)點(diǎn)出發(fā)，按照以下步驟訪問樹中的每個(gè)結(jié)點(diǎn)：* 1. 優(yōu)先進(jìn)入當(dāng)前結(jié)點(diǎn)的左子樹，以同樣的步驟遍歷左子樹中的結(jié)點(diǎn)；* 2. 如果當(dāng)前結(jié)點(diǎn)沒有左子樹，則進(jìn)入它的右子樹，以同樣的步驟遍歷右子樹中的結(jié)點(diǎn)；* 3. 直到當(dāng)前結(jié)點(diǎn)的左子樹和右子樹都遍歷完后，才訪問該結(jié)點(diǎn)。** 4, 5, 2, 6, 7, 3, 1* @param treeNode*/public static void postTraverseForNoRecursion(TreeNode treeNode){TreeNode curr = treeNode;LinkedList<TreeNode> stack = new LinkedList<>();// 定義最后一次出棧節(jié)點(diǎn)，防止陷入重復(fù)執(zhí)行TreeNode pop = null;while (curr != null || !stack.isEmpty()){if (curr != null){stack.push(curr);curr = curr.left;}else {// peek方法是查詢棧頂數(shù)據(jù)，但是不彈出TreeNode last = stack.peek();// last.right == pop 如果相等，那就說明已經(jīng)執(zhí)行過該右子節(jié)點(diǎn)了，這個(gè)條件是防止有右子節(jié)點(diǎn)的數(shù)據(jù)陷入死循環(huán)中if (last.right == null || last.right == pop){pop = stack.pop();printTreeNode(pop);}else {curr = last.right;}}}}

層次遍歷

流程描述

上面這棵樹一共有 3 層，根結(jié)點(diǎn)位于第一層，以此類推。

所謂層次遍歷二叉樹，就是從樹的根結(jié)點(diǎn)開始，一層一層按照從左往右的次序依次訪問樹中的結(jié)點(diǎn)。

層次遍歷用阻塞隊(duì)列存儲(chǔ)的二叉樹，可以借助隊(duì)列存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，具體方案是：

1. 將根結(jié)點(diǎn)入隊(duì)；
2. 從隊(duì)列的頭部提取一個(gè)結(jié)點(diǎn)并訪問它，將該結(jié)點(diǎn)的左孩子和右孩子依次入隊(duì)；
3. 重復(fù)執(zhí)行第 2 步，直至隊(duì)列為空；

假設(shè)將圖 1 中的二叉樹存儲(chǔ)到鏈表中，那么層次遍歷的過程是：

根結(jié)點(diǎn) 1 入隊(duì)（1）；
根結(jié)點(diǎn) 1 出隊(duì)并訪問它，然后將 1 的左孩子 2 和右孩子 3 依次入隊(duì)（3, 2）；
將結(jié)點(diǎn) 2 出隊(duì)并訪問它，然后將 2 的左孩子 4 和右孩子 5 依次入隊(duì)（5,4,3）；
將結(jié)點(diǎn) 3 出隊(duì)并訪問它，然后將 3 的左孩子 6 和右孩子 7 依次入隊(duì)（7,6,5,4）；
根結(jié)點(diǎn) 4 出隊(duì)并訪問它，然后將 4 的左孩子（無）和右孩子（無）依次入隊(duì)（7,6,5）；
將結(jié)點(diǎn) 5 出隊(duì)并訪問它，然后將 5 的左孩子（無）和右孩子（無）依次入隊(duì)（7,6）；
將結(jié)點(diǎn) 6 出隊(duì)并訪問它，然后將 6 的左孩子（無）和右孩子（無）依次入隊(duì)（7）；  
將結(jié)點(diǎn) 7 出隊(duì)并訪問它，然后將 6 的左孩子（無）和右孩子（無）依次入隊(duì)（）；
隊(duì)列為空，層次遍歷結(jié)束

最終，后序遍歷圖 1 中的二叉樹，訪問各個(gè)結(jié)點(diǎn)的順序是：

1 2 3 4 5 6 7

代碼實(shí)現(xiàn)

 /*** 層次遍歷* 所謂層次遍歷二叉樹，就是從樹的根結(jié)點(diǎn)開始，一層一層按照從左往右的次序依次訪問樹中的結(jié)點(diǎn)。* 1. 將根結(jié)點(diǎn)入隊(duì)；* 2. 從隊(duì)列的頭部提取一個(gè)結(jié)點(diǎn)并訪問它，將該結(jié)點(diǎn)的左孩子和右孩子依次入隊(duì)；* 3. 重復(fù)執(zhí)行第 2 步，直至隊(duì)列為空；* @param treeNode*/public static void levelTraverseForRecursion(TreeNode treeNode){if (treeNode != null){LinkedBlockingQueue<TreeNode> queue = new LinkedBlockingQueue<>(10);queue.offer(treeNode);doPushQueue(queue);}}/*** 使用阻塞隊(duì)列實(shí)現(xiàn)二叉樹層次遍歷* 阻塞隊(duì)列的特點(diǎn)就是先進(jìn)先出* @param nowQueue*/private static void doPushQueue(LinkedBlockingQueue<TreeNode> nowQueue){if (nowQueue.isEmpty()){return;}// 從阻塞隊(duì)列中彈出TreeNode poll = nowQueue.poll();while (poll != null){printTreeNode(poll);// 如果左子節(jié)點(diǎn)不為null, 則入隊(duì)列if (poll.left != null){nowQueue.offer(poll.left);}// 如果右子節(jié)點(diǎn)不為null, 則入隊(duì)列if (poll.right != null){nowQueue.offer(poll.right);}// 從阻塞隊(duì)列中彈出poll = nowQueue.poll();}}

總結(jié)

總結(jié)各個(gè)遍歷類型的流程

前序遍歷：根節(jié)點(diǎn) - 左節(jié)點(diǎn) - 右節(jié)點(diǎn)
中序遍歷：左節(jié)點(diǎn) - 根節(jié)點(diǎn) - 右節(jié)點(diǎn)
后序遍歷：左節(jié)點(diǎn) - 右節(jié)點(diǎn) - 根節(jié)點(diǎn)
層次遍歷：從根節(jié)點(diǎn)開始一層一層的遍歷（左節(jié)點(diǎn)-右節(jié)點(diǎn)）