算法-二叉樹的三種遍歷方式

2019-11-06 06:01:28

字體：大中小

來源：轉載

供稿：網友

偶然翻到了去年三月份自己寫的一份關于二叉樹的三種遍歷方式（準確的說，是6中，包含遞歸和非遞歸），好久不復習關于算法相關的知識，這些基礎還都是在前年備戰考研的過程中準備的。希望自己以后多多復習之前的只是，溫故而知新，不要撿起芝麻丟了西瓜。廢話不多說，還是直接上代碼： 1.Node節點類

package BinTreeTraverse;/** * 創建人:劉星創建日期:2017-3-7 下午4:53:51 * 功能描述:(node節點類) * @version V1.0 */public class Node { Node leftChild;//節點的左孩子節點 Node rightChild;//節點的右孩子節點 int data;//節點存儲的數據 Node(int newData) {//構造函數，默認左右孩子都為空 leftChild = null; rightChild = null; data = newData; }}

2.遍歷實現類

package BinTreeTraverse;import java.util.LinkedList; import java.util.List; import java.util.Stack;/** * 創建人:劉星創建日期:2017-3-7 下午4:51:37 * 功能描述:(遍歷二叉樹實現類) * @version V1.0 */public class BinTreeTraverse { PRivate int[] array = { 1, 2, 3, 4, 5, 6, 7, 8,9};//由于節點存儲數據類型為int，這里定義一個int的數組 private static List<Node> nodeList = null;//節點列表，通過左右指針關系構建二叉樹的父子關系 /** * * 創建人:劉星創建日期:2017-3-7下午4:57:56 * 功能描述:(將數組節點插入到二叉樹中，構造一棵二叉樹) * @param 對方法中某參數的說明 * @return 對方法返回值的說明 * @exception 對方法可能拋出的異常進行說明 * @version 1.0 */ public void createBinTree() { nodeList = new LinkedList<Node>(); // 將一個數組的值依次轉換為Node節點 for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) { nodeList.add(new Node(array[nodeIndex])); } // 對前lastParentIndex-1個父節點按照父節點與孩子節點的數字關系建立二叉樹 for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) { // 左孩子 nodeList.get(parentIndex).leftChild = nodeList .get(parentIndex * 2 + 1); // 右孩子 nodeList.get(parentIndex).rightChild = nodeList .get(parentIndex * 2 + 2); } // 最后一個父節點:因為最后一個父節點可能沒有右孩子，所以單獨拿出來處理 int lastParentIndex = array.length / 2 - 1; // 左孩子 nodeList.get(lastParentIndex).leftChild = nodeList .get(lastParentIndex * 2 + 1); // 右孩子,如果數組的長度為奇數才建立右孩子 if (array.length % 2 == 1) { nodeList.get(lastParentIndex).rightChild = nodeList .get(lastParentIndex * 2 + 2); } } /** * 先序遍歷 * * 這三種不同的遍歷結構都是一樣的，只是先后順序不一樣而已 * * @param node * 遍歷的節點 */ public static void preOrderTraverse(Node node) { if (node == null) return; System.out.print(node.data + " ");//這里用控制臺輸出代表訪問當前節點 preOrderTraverse(node.leftChild); preOrderTraverse(node.rightChild); } /** * 中序遍歷 * * 這三種不同的遍歷結構都是一樣的，只是先后順序不一樣而已 * * @param node * 遍歷的節點 */ public static void inOrderTraverse(Node node) { if (node == null) return; inOrderTraverse(node.leftChild); System.out.print(node.data + " "); inOrderTraverse(node.rightChild); } /** * 后序遍歷 * * 這三種不同的遍歷結構都是一樣的，只是先后順序不一樣而已 * * @param node * 遍歷的節點 */ public static void postOrderTraverse(Node node) { if (node == null) return; postOrderTraverse(node.leftChild); postOrderTraverse(node.rightChild); System.out.print(node.data + " "); } /** * 先序遍歷非遞歸算法 * 借助棧來實現 * @param args */ public static void preOrderTraverseWithoutRec(Node node){ if (node == null) return; Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty()|| node != null){ if(node != null){ System.out.print(node.data + " "); stack.push(node); node = node.leftChild; }else{ node = stack.pop(); node = node.rightChild; } } } /** * 中序遍歷非遞歸算法 * * @param args */ public static void inOrderTraverseWithoutRec(Node node){ if (node == null) return; Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty()|| node != null){ if(node != null){ stack.push(node); node = node.leftChild; }else{ node = stack.pop(); System.out.print(node.data + " "); node = node.rightChild; } } } /** * 后序遍歷非遞歸算法 * * @param args */ public static void postOrderTraverseWithoutRec(Node node){ if (node == null) return; Stack<Node> stack = new Stack<Node>(); while(!stack.isEmpty()|| node != null){ if(node != null){ stack.push(node); node = node.leftChild; }else{ node = stack.pop(); System.out.print(node.data+" "); node = node.rightChild; } } } public static void main(String[] args) { BinTreeTraverse binTree = new BinTreeTraverse(); binTree.createBinTree(); // nodeList中第0個索引處的值即為根節點 Node root = nodeList.get(0); System.out.println("先序遍歷："); preOrderTraverse(root); System.out.println(); System.out.println("中序遍歷："); inOrderTraverse(root); System.out.println(); System.out.println("后序遍歷："); postOrderTraverse(root); System.out.println(); System.out.println("先序遍歷非遞歸算法："); preOrderTraverseWithoutRec(root); System.out.println(); System.out.println("中序遍歷非遞歸算法："); inOrderTraverseWithoutRec(root); System.out.println(); System.out.println("后序遍歷非遞歸算法："); postOrderTraverseWithoutRec(root); System.out.println(); } }

3.總結熟練并掌握算法的核心思想是關鍵。記得當時備戰考研時看的書，里面多是用c來實現的。當時并不太明白好多細節?，F在能熟練的用java復現也算是自己的一種成長吧。在之后的學習之路中我應該多多關注算法并和大家分享算法的實現。

上一篇：【面試題】劍指offer 17

下一篇：Switch能否用String做參數？