二叉樹的遍歷實現遞歸與非遞歸
- 2020 年 3 月 9 日
- 筆記
本文實現了二叉樹的深度遍歷演算法，分為遞歸與非遞歸
遞歸的實現非常簡單，基本上沒啥難度
非遞歸的實現需要根據遍歷的順序，將遞歸轉換成循環
程式碼中的二叉樹如下
遞歸
遞歸的實現很簡單，此處不做過多贅述
package cn.lillcol.agst.test; /** * 定義 結點數據結構 */ public class Node { // 數據域 String data = "null"; // 左孩子 Node leftChild; // 右孩子 Node rightChild; // 是否被訪問 boolean isVisit = false; public void setIsVisit(boolean isVisit) { this.isVisit = isVisit; } public boolean getisVisit() { return this.isVisit; } public Node(String data) { this.data = data; } public void setData(String data) { this.data = data; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } @Override public String toString() { return this.data; } } package cn.lillcol.agst.test; /** * 二叉樹遍歷案例遞歸版本 * * @author lillcol * @date 2020-01-16 23：56：51 */ public class BTreeTestRecursion { public static void main(String[] args) { BTreeTestRecursion bTreeTestRecursion = new BTreeTestRecursion(); Node bTree = bTreeTestRecursion.createBTree(); System.out.print("前序遍歷："); bTreeTestRecursion.preOrderTraverse(bTree); System.out.print("n中序遍歷："); bTreeTestRecursion.inOrderTraverse(bTree); System.out.print("n後序遍歷："); bTreeTestRecursion.postOrderTraverse(bTree); } /** * 生成一棵樹 * * @return */ public Node createBTree() { Node A = new Node("A"); Node B = new Node("B"); Node C = new Node("C"); Node D = new Node("D"); Node E = new Node("E"); Node F = new Node("F"); Node G = new Node("G"); Node H = new Node("H"); Node I = new Node("I"); A.setLeftChild(B); A.setRightChild(C); B.setLeftChild(D); C.setLeftChild(E); C.setRightChild(F); D.setLeftChild(G); D.setRightChild(H); E.setRightChild(I); return A; } /** * 前序遍歷遞歸版本 * * @param t */ public void preOrderTraverse(Node t) { if (t == null) return; System.out.print(t.data + "->"); preOrderTraverse(t.leftChild); preOrderTraverse(t.rightChild); } /** * 中序遍歷 遞歸版本 * * @param t */ public void inOrderTraverse(Node t) { if (t == null) return; inOrderTraverse(t.leftChild); System.out.print(t.data + "->"); inOrderTraverse(t.rightChild); } /** * 後續遍歷 遞歸版本 * * @param t */ public void postOrderTraverse(Node t) { if (t == null) return; postOrderTraverse(t.leftChild); postOrderTraverse(t.rightChild); System.out.print(t.data + "->"); } } 非遞歸
非遞歸的實現比起遞歸相對複雜些。
核心是利用棧的特性，記錄訪問過的結點或輸出的結點
非遞歸的實現中，先序遍歷、中序遍歷是比較簡單的，只要按照便利的順序結合程式碼的注釋基本就可以理解了。
比較難的後續遍歷，在實現的過程中發現，如果要按照訪問順序來進行實現，很複雜。
有些實現方式是通過增加一個標誌位標記該借點是否訪問過，但是卻有問題：比如需要考慮很多子樹的情況，判斷情況特別多，只要少一個情況就會出錯。
後面查看資料還有一個實現的方式相對簡單很多，實現如下：
後序遍歷可以看作逆先序遍歷，此處有兩個關鍵：
- 結果是先序遍歷的逆序
- 此處的先序遍歷不是從左到右的先序遍歷，是從右到做的先序遍歷，具體如下圖
下面對比觀察一下結果：
package cn.lillcol.agst.test; import java.util.Stack; /*** * 二叉樹層次遍歷的非遞歸實現版本 * @author lillcol 20200308 */ public class BTreeTestNotRecursion { public static void main(String[] args) throws InterruptedException { BTreeTestNotRecursion bTreeTestNotRecursion = new BTreeTestNotRecursion(); Node bTree = bTreeTestNotRecursion.createBTree(); bTreeTestNotRecursion.inOrderTraverse(bTree); bTreeTestNotRecursion.preOrderTraverse(bTree); bTreeTestNotRecursion.postOrderTraverse(bTree); } /** * 前序遍歷 非遞歸版本 * * @param t */ public void preOrderTraverse(Node t) { if (t == null) return; Stack<Node> stack = new Stack<>(); // 此處出了t不為空，還需要棧也不為空，否則會停在第一次遍歷到右節點的位置 while (t != null || !stack.empty()) { // 遍歷到樹的最左邊節點 while (t != null) { stack.push(t);//記錄遍歷過的節點 System.out.print(t.data + "->");//先序遍歷，首先輸出父節點，所以此處需要輸出 t = t.leftChild;//遍歷父節點後，下一個遍歷的節點為左節點 } if (!stack.empty()) { // 當遍歷完左節點，需要遍歷右節點 t = stack.pop().rightChild; } } } /** * 中序遍歷 非遞歸版本 * * @param t */ public void inOrderTraverse(Node t) { if (t == null) return; Stack<Node> stack = new Stack<>(); //當前節點不為空，或棧中有元素 while (t != null || !stack.empty()) { //一直遍歷左子樹，直到某結點的左子樹為null，說明到了最下邊的左子樹 while (t != null) { //將每一個便利的左子樹入棧 stack.push(t); t = t.leftChild; } //當遍歷到最下邊的左子樹，就需要開始出棧了 if (!stack.empty()) { //棧頂元素出棧 Node top = stack.pop(); System.out.print(top.toString() + "->"); //遍歷因為是中序遍歷，在輸出一個結點後，接下來判斷該結點的右子樹，這和之前一樣相當於是一新的樹，重複之前的操作即可 t = top.rightChild; } } } /** * 後續遍歷 非遞歸版本 * 核心：後續遍歷就是 逆先序遍歷 （先序遍歷的順序為父->右結點->左結點：和一般的剛好相反） * 所以程式碼實現需要兩個棧，一個進行節點的先序遍歷，另一個記錄輸出內容（因為是逆序，所以根據棧的特性，最後在遍歷stack2即是最終的後續遍歷結果） * * @param t */ public void postOrderTraverse(Node t) { if (t == null) return; Stack<Node> stack = new Stack<>(); Stack<Node> stack2 = new Stack<>(); while (t != null || !stack.empty()) { while (t != null) { stack.push(t);//記錄已經訪問結點 // System.out.print(t.data + "->");正常先序遍歷該在此處輸出 stack2.push(t);//記錄本該輸出的部分 t = t.rightChild; } if (!stack.empty()) { t = stack.pop().leftChild; } } // 輸出stack2中的記錄即為後續遍歷結果 while (!stack2.empty()) { System.out.print(stack2.pop().data + "->"); } } /** * 生成一棵樹 * * @return */ public Node createBTree() { Node A = new Node("A"); Node B = new Node("B"); Node C = new Node("C"); Node D = new Node("D"); Node E = new Node("E"); Node F = new Node("F"); Node G = new Node("G"); Node H = new Node("H"); Node I = new Node("I"); A.setLeftChild(B); A.setRightChild(C); B.setLeftChild(D); C.setLeftChild(E); C.setRightChild(F); D.setLeftChild(G); D.setRightChild(H); E.setRightChild(I); return A; } } 本文為原創文章，轉載請註明出處！！！
