Java递推遍历访问二叉树

引入

学习二叉树离不开访问遍历它，最简单的方法是递归遍历来实现，递归实现简单，但递推偏复杂些。

以下的递推代码是从MOOC上浙江大学的数据结构学习的，可以点开链接系统学习 数据结构-浙江大学 不过它是用C++写的，我这用Java简单实现下并加上些注释希望能帮助到一些人更容易理解。

Java代码

DisPlayBinaryTree.java import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class DisPlayBinaryTree { /* 先序思路： 1.遇到一个节点，就访问它，并遍历它的左子树 2.当左子树遍历完后，从栈顶弹出节点 3.然后变换为它的右节点再去先序遍历该节点的子树 */ // 1. 先序 public void preorder(TreeNode curnode){ Stack<TreeNode> stack = new Stack<>(); while(curnode != null || !stack.isEmpty()){ // 依次把左子树压入栈并访问当前节点 while(curnode != null){ System.out.print(curnode.val+" ");// 访问 stack.push(curnode); curnode = curnode.leftNode; } // 遍历完左子树，弹出栈顶 curnode = stack.pop(); // 变换为它的右节点继续先序遍历 curnode = curnode.rightNode; } } /* 中序思路：（与先序思路差不多） 1.遇到一个节点，就把它压入栈，并遍历它的左子树 2.当左子树遍历完后，从栈顶弹出节点并访问它 3.然后变换为它的右节点再去中序遍历该节点的子树 */ public void midorder(TreeNode curnode){ Stack<TreeNode> stack = new Stack<>(); while(curnode != null || !stack.isEmpty()){ // 依次把左子树压入栈 while(curnode != null){ stack.push(curnode); curnode = curnode.leftNode; } // 遍历完左子树，弹出栈顶并访问 curnode = stack.pop(); System.out.print(curnode.val+" "); // 变换为它的右节点继续中序遍历 curnode = curnode.rightNode; } } /* 后序思路：（与前两者稍有不同，但框架差不多） 1.遇到一个节点，把它压入栈，并遍历它的左子树 2.当左子树遍历后，从栈顶弹出节点，判断是否输出的时刻（自己没有右节点，或者，自己的右节点被访问过了就输出继续2步骤，否则进入3） 3.把这弹出的节点再次入栈，变换为它的右节点再继续后序遍历该节点的子树 */ public void lastorder(TreeNode curnode){ Stack<TreeNode> stack = new Stack<>(); TreeNode lastnode = null;// 记录上一次访问的节点 while(curnode != null || !stack.isEmpty()){ // 依次把左子树压入栈 while(curnode != null){ stack.push(curnode); curnode = curnode.leftNode; } // 遍历完左子树，弹出栈顶 curnode = stack.pop(); // 当前节点可以输出条件：它的右节点为空，或者，它从它的右节点返回回来 if(curnode.rightNode == null || curnode.rightNode == lastnode){ System.out.print(curnode.val+" "); lastnode = curnode; curnode = null;// 访问完就置空了,免得再次把它的左子树压入栈 }else{ // 没到访问时机，再次把这节点压入栈 stack.push(curnode); // 变化为它的右节点，继续后序遍历 curnode = curnode.rightNode; } } } public static void main(String[] args) { // 构建树结构 TreeNode root = new TreeNode(6); TreeNode node1 = new TreeNode(4); TreeNode node2 = new TreeNode(3); TreeNode node3 = new TreeNode(5); TreeNode node4 = new TreeNode(8); TreeNode node5 = new TreeNode(7); TreeNode node6 = new TreeNode(9); TreeNode node7 = new TreeNode(5); root.leftNode = node1; root.leftNode.leftNode = node2; root.leftNode.rightNode = node3; root.rightNode = node4; root.rightNode.leftNode = node5; root.rightNode.rightNode = node6; root.leftNode.rightNode.rightNode = node7; DisPlayBinaryTree dt = new DisPlayBinaryTree(); // 先序遍历 dt.preorder(root); System.out.println(); // 中序遍历 dt.midorder(root); System.out.println(); // 后序遍历 dt.lastorder(root); System.out.println(); // 层次遍历 dt.levelorder(root); } /* 补一个，用队列层次遍历 1.先读取队列的队首节点，并且访问它 2.把它的左右节点添加到队列中 */ public void levelorder(TreeNode curnode){ Queue<TreeNode> que = new LinkedList<TreeNode>(); que.add(curnode); while(!que.isEmpty()){ curnode = que.poll(); System.out.print(curnode.val+" "); if(curnode.leftNode != null){ que.add(curnode.leftNode); } if(curnode.rightNode != null){ que.add(curnode.rightNode); } } } } TreeNode.java public class TreeNode { TreeNode leftNode; TreeNode rightNode; int val; public TreeNode() { // TODO Auto-generated constructor stub } public TreeNode(int vl) { // TODO Auto-generated constructor stub this.val = vl; } public TreeNode getLeftNode() { return leftNode; } public void setLeftNode(TreeNode leftNode) { this.leftNode = leftNode; } public TreeNode getRightNode() { return rightNode; } public void setRightNode(TreeNode rightNode) { this.rightNode = rightNode; } public int getVal() { return val; } public void setVal(int val) { this.val = val; } }