二叉树的遍历（Java版）

二叉树的非递归遍历，主要借助于“栈”后进先出的特性来保存节点的顺序，先序遍历和中序遍历相对来说比较简单，重点理解后序遍历。

先来看一下节点类型：

//二叉树的节点类型 private class Node{ int data; //节点值 Node leftChild; //左孩子 Node rightChild; //右孩子 public Node(int data) { this.data=data; } }

一、非递归版本

1、先序遍历

1.先将根节点入栈 2.访问根节点 3.如果根节点存在右孩子，则将右孩子入栈 4.如果根节点存在左孩子，则将左孩子入栈（注意：一定是右孩子先入栈，然后左孩子入栈） 5.重复2-4

public void preOrder(Node Root) { if(Root==null) { System.out.println("空树"); return; } Node tmp=Root; Stack<Node> s=new Stack<Node>(); s.push(tmp); //根节点入栈 while(!s.empty()) { //1.访问根节点 Node p=s.pop(); System.out.print(p.data+" "); //2.如果根节点存在右孩子，则将右孩子入栈 if(p.rightChild!=null) { s.push(p.rightChild); } //3.如果根节点存在左孩子，则将左孩子入栈 if(p.leftChild!=null) { s.push(p.leftChild); } } System.out.println(); }

2、中序遍历

1.先将根节点入栈 2.将当前节点的所有左孩子入栈，直到左孩子为空 3.访问栈顶元素，如果栈顶元素存在右孩子，则继续第2步 4.重复第2、3步，直到栈为空并且所有的节点都被访问

public void inOrder(Node Root) { if(Root==null) { System.out.println("空树"); return; } Node tmp=Root; Stack<Node> s=new Stack<Node>(); while(tmp!=null || !s.empty()) { //1.将根节点入栈 //2.将所有左孩子入栈 while(tmp!=null) { s.push(tmp); tmp=tmp.leftChild; } //3.访问栈顶元素 tmp=s.pop(); System.out.print(tmp.data+" "); //4.如果栈顶元素存在右孩子，则将右孩子赋值给tmp，也就是将右孩子入栈 if(tmp.rightChild!=null) { tmp=tmp.rightChild; } //否则，将tmp置为null，表示下次要访问的是栈顶元素 else { tmp=null; } } System.out.println(); }

3、后序遍历

1.根节点入栈 2.将根节点的左子树入栈，直到最左，没有左孩子为止 3.得到栈顶元素的值，先不访问，判断栈顶元素是否存在右孩子，如果存在并且没有被访问（多一个标记上一次访问的节点），则将右孩子入栈，否则，就访问栈顶元素

public void postOrder(Node Root) { if(Root==null) { System.out.println("空树"); return; } Node tmp=Root; //当前节点 Node prev=null; //上一次访问的节点 Stack<Node> s=new Stack<Node>(); while(tmp!=null || !s.empty()) { //1.将根节点及其左孩子入栈 while(tmp!=null) { s.push(tmp); tmp=tmp.leftChild; } if(!s.empty()) { //2.获取栈顶元素值 tmp=s.peek(); //3.没有右孩子，或者右孩子已经被访问过 if(tmp.rightChild==null || tmp.rightChild==prev) { //则可以访问栈顶元素 tmp=s.pop(); System.out.print(tmp.data+" "); //标记上一次访问的节点 prev=tmp; tmp=null; } //4.存在没有被访问的右孩子 else { tmp=tmp.rightChild; } } } System.out.println(); }

二、递归版本

1、前序遍历

public void preOrder(TreeNode node) { if (node != null) { System.out.print(node.data+" "); preOrder(node.leftChild); preOrder(node.rightChild); } }

2、中序遍历

public void inOrder(TreeNode node) { if (node != null) { inOrder(node.leftChild); System.out.print(node.data+" "); inOrder(node.rightChild); } }

3、后序遍历

public void postOrder(TreeNode node) { if (node != null) { postOrder(node.leftChild); postOrder(node.rightChild); System.out.print(node.data+" "); } }

参考 1、二叉树的非递归遍历（java版）