二叉树遍历：前序、中序、后序

本文主要是介绍二叉树遍历：前序、中序、后序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 二叉树三种遍历的递归、非递归实现

首先定义一棵二叉树的结构：

/*** @Description 二叉树* @Author lilong* @Date 2019-02-27 10:23*/
public class BinTreeNode {private int data;private BinTreeNode left;private BinTreeNode right;public int getData() {return data;}public void setData(int data) {this.data = data;}public BinTreeNode getLeft() {return left;}public void setLeft(BinTreeNode left) {this.left = left;}public BinTreeNode getRight() {return right;}public void setRight(BinTreeNode right) {this.right = right;}
}

然后是3种遍历的递归、非递归实现：

import java.util.Stack;/*** @Description 前序遍历、中序遍历、后序遍历* @Author lilong* @Date 2019-02-27 11:26*/
public class TraverseBinTree {/* 递归 *//*** 前序遍历（递归）* @param root*/public void preOrderRecursive(BinTreeNode root) {if (root == null) {return;}System.out.println(root.getData());preOrderRecursive(root.getLeft());preOrderRecursive(root.getRight());}/*** 中序遍历（递归）* @param root*/public void inOrderRecursive(BinTreeNode root) {if (root == null) {return;}preOrderRecursive(root.getLeft());System.out.println(root.getData());preOrderRecursive(root.getRight());}/*** 后序遍历（递归）* @param root*/public void postOrderRecursive(BinTreeNode root) {if (root == null) {return;}preOrderRecursive(root.getLeft());preOrderRecursive(root.getRight());System.out.println(root.getData());}/* 非递归 *//*** 前序遍历* @param root*/public void preOrder(BinTreeNode root) {if (root == null) {return;}Stack<BinTreeNode> stack = new Stack<BinTreeNode>();while (true) {while (root != null) {System.out.println(root.getData());stack.push(root);root = root.getLeft();}if (stack.isEmpty()) {break;}root = stack.pop();root = root.getRight();}}/*** 中序遍历* @param root*/public void inOrder(BinTreeNode root) {if (root == null) {return;}Stack<BinTreeNode> stack = new Stack<BinTreeNode>();while (true) {while (root != null) {stack.push(root);root = root.getLeft();}if (stack.isEmpty()) {break;}root = stack.pop();System.out.println(root.getData());root = root.getRight();}}/*** 后序遍历* @param root*/public void postOrder(BinTreeNode root) {if (root == null) {return;}Stack<BinTreeNode> stack = new Stack<BinTreeNode>();while (true) {if (root != null) {stack.push(root);root = root.getLeft();} else {if (stack.isEmpty()) {System.out.println("Stack is empty.");return;} else {if (stack.peek().getRight() == null) {root = stack.pop();System.out.println(root.getData());if (root == stack.peek().getRight()) {System.out.println(stack.peek().getData());stack.pop();}}if (!stack.isEmpty()) {root = stack.peek().getRight();} else {root = null;}}}}}
}

最后测试下：

/*** @Description 测试* @Author lilong* @Date 2019-02-27 11:35*/
public class Test {public static void main(String[] args) {BinTreeNode node1 = new BinTreeNode();node1.setData(2);node1.setLeft(null);node1.setRight(null);BinTreeNode node2 = new BinTreeNode();node2.setData(3);node2.setLeft(null);node2.setRight(null);BinTreeNode root = new BinTreeNode();root.setData(1);root.setLeft(node1);root.setRight(node2);TraverseBinTree traverseBinTree = new TraverseBinTree();
//        traverseBinTree.preOrderRecursive(root);
//        traverseBinTree.inOrderRecursive(root);
//        traverseBinTree.postOrderRecursive(root);
//        traverseBinTree.preOrder(root);
//        traverseBinTree.inOrder(root);traverseBinTree.postOrder(root);}
}