package com.shiyeqiang.tree;import java.util.Stack;public class BiTree {public static void main(String[] args) {// 首先構造葉子節點BiTree leafA1 = new BiTree(4);BiTree leafA2 = new BiTree(5);BiTree leafB1 = new BiTree(6);BiTree leafB2 = new BiTree(7);// 構建二叉樹的結構BiTree treeA = new BiTree(2, leafA1, leafA2);BiTree treeB = new BiTree(3, leafB1, leafB2);BiTree tree = new BiTree(1, treeA, treeB);System.out.println("遞歸前序遍歷二叉樹結果: ");preOrder(tree);System.out.println();System.out.println("非遞歸前序遍歷二叉樹結果: ");iterativePreOrder(tree);System.out.println();System.out.println("非遞歸中序遍歷二叉樹結果: ");iterativeInOrder(tree);System.out.println();System.out.println("遞歸興許遍歷二叉樹結果: ");iterativePostOrder(tree);}private BiTree leftTree;private BiTree rightTree;private Object data;public BiTree() {}public BiTree(Object data) {this.data = data;}public BiTree(Object data, BiTree leftTree, BiTree rightTree) {this.data = data;this.leftTree = leftTree;this.rightTree = rightTree;}public static void visit(Object data) { // 訪問二叉樹的數據System.out.print(data + " ");}public static void preOrder(BiTree tree) {// 遞歸實現前序遍歷二叉樹if (tree != null) {visit(tree.data);if (tree.leftTree != null)preOrder(tree.leftTree);if (tree.rightTree != null)preOrder(tree.rightTree);}}public static void inOrder(BiTree tree) {// 遞歸實現中序遍歷二叉樹(左-根--右邊)if (tree != null) {if (tree.leftTree != null)inOrder(tree.leftTree);visit(tree.data);if (tree.rightTree != null)inOrder(tree.rightTree);}}public static void postOrder(BiTree tree) {// 遞歸實現后序遍歷二叉樹if (tree != null) {if (tree.leftTree != null)postOrder(tree.leftTree);if (tree.rightTree != null)postOrder(tree.rightTree);visit(tree.data);}}// 非遞歸實現前序遍歷，根----左子樹---右子樹public static void iterativePreOrder(BiTree tree) {Stack<BiTree> stack = new Stack<BiTree>();if (tree != null) {stack.push(tree);while (!stack.isEmpty()) {tree = stack.pop();visit(tree.data);if (tree.rightTree != null)stack.push(tree.rightTree); // 首先必須是右子樹入棧，if (tree.leftTree != null)stack.push(tree.leftTree);}}}// 非遞歸實現中序遍歷，左---根---右public static void iterativeInOrder(BiTree tree) {Stack<BiTree> stack = new Stack<BiTree>();// 主要是依據入棧以及出棧的思想實現的//以一個1,2,3,4,5,6,7的滿二叉樹為例：中序遍歷例如以下：//右子樹3入棧，根節點1入棧，右子樹5入棧，根節點2入棧，根節點4入棧。//左子樹4出棧，根節點2出棧，5出戰，依照上述規則又一次遍歷右子樹5while (tree != null) {while (tree != null) {if (tree.rightTree != null)stack.push(tree.rightTree);// 當前節點右子入棧stack.push(tree);// 當前節點入棧tree = tree.leftTree;}tree = stack.pop();// 以下為訪問的是葉子節點while (!stack.empty() && tree.rightTree == null) {visit(tree.data);tree = stack.pop();}visit(tree.data);if (!stack.empty()) {tree = stack.pop(); // 下一次遍歷,事實上在這個時候遍歷的是右子樹把} else {tree = null;}}}// 非遞歸實現后序遍歷public static void iterativePostOrder(BiTree tree) {BiTree tempTree = tree;Stack<BiTree> stack = new Stack<BiTree>();while (tree != null) {// 左子樹入棧for (; tree.leftTree != null; tree = tree.leftTree)stack.push(tree);// 當前節點無右子或右子已經輸出while (tree != null&& (tree.rightTree == null || tree.rightTree == tempTree)) {visit(tree.data);tempTree = tree;// 記錄上一個已輸出節點if (stack.empty())return;tree = stack.pop(); //一般處理根節點的時候均是先出戰 ，然后再入棧}// 處理右子stack.push(tree);tree = tree.rightTree;}} }

轉載于:https://www.cnblogs.com/mfrbuaa/p/4201404.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的二叉树三种遍历（递归以及非递归实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。