</pre><p></p><p>参考网上一些资料测试整理了一下二叉树遍历的Java实现代码。</p>二叉树三种遍历方式：先序遍历、中序遍历、后序遍历。<p>首先定义二叉树类：</p><p></p><pre code_snippet_id="422510" snippet_file_name="blog_20140708_2_1633299" name="code" class="java">package mm.test.tree;
public class BinaryTree {
char data;//根节点
BinaryTree leftChild;//左孩子
BinaryTree rightChild;//右孩子
public BinaryTree() {
}
public void visit() {
System.out.println(this.data);
}
public BinaryTree(char data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public BinaryTree getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTree leftChild) {
this.leftChild = leftChild;
}
public BinaryTree getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTree rightChild) {
this.rightChild = rightChild;
}
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
}
先序遍历思想：根左右。首先遍历根节点，然后遍历左子树和右子树。
package mm.test.tree;
import java.util.Stack;
public class VisitBinaryTree {
//先序遍历非递归算法
private void preOrder(BinaryTree root) {
if(root!=null) {
Stack<BinaryTree> stack = new Stack<BinaryTree>();
for (BinaryTree node = root; !stack.empty() || node != null;) {
//当遍历至节点位空的时候出栈
if(node == null) {
node = stack.pop();
}
node.visit();
//遍历右孩子存入栈内
if(node.getRightChild()!=null) {
stack.push(node.getRightChild());
}
//遍历左子树节点
node = node.getLeftChild();
}
}
}
//先序遍历递归算法
public void preOrderRecursion(BinaryTree root) {
if(root!=null) {
root.visit();
preOrderRecursion(root.getLeftChild());
preOrderRecursion(root.getRightChild());
}
}
}
测试代码：
public static void main(String args[]) {
BinaryTree node = new BinaryTree('A');
<span style="white-space:pre"></span> BinaryTree root = node;
<span style="white-space:pre"></span> BinaryTree nodeL1;
<span style="white-space:pre"></span> BinaryTree nodeL;
<span style="white-space:pre"></span> BinaryTree nodeR;
<span style="white-space:pre"></span> node.setLeftChild(new BinaryTree('B'));
<span style="white-space:pre"></span> node.setRightChild(new BinaryTree('C'));
<span style="white-space:pre"></span> nodeL1 = node.getLeftChild();
<span style="white-space:pre"></span> nodeL1.setLeftChild(new BinaryTree('D'));
<span style="white-space:pre"></span> nodeL1.setRightChild(new BinaryTree('E'));
<span style="white-space:pre"></span> nodeL = nodeL1.getLeftChild();
<span style="white-space:pre"></span> nodeL.setLeftChild(new BinaryTree('F'));
<span style="white-space:pre"></span> node = node.getRightChild();
<span style="white-space:pre"></span> node.setLeftChild(new BinaryTree('G'));
<span style="white-space:pre"></span> node.setRightChild(new BinaryTree('H'));
<span style="white-space:pre"></span> nodeR = node.getLeftChild();
<span style="white-space:pre"></span> nodeR.setLeftChild(new BinaryTree('I'));
<span style="white-space:pre"></span> nodeR.setRightChild(new BinaryTree('J'));
<span style="white-space:pre"></span> VisitBinaryTree vt= new VisitBinaryTree();
//先序遍历递归和非递归测试
vt.preOrder(root);
vt.preOrderRecursion(root);
}
中序遍历算法：
//中序遍历的非递归算法测试代码：
public void inOrder(BinaryTree root) {
if(root!=null) {
Stack<BinaryTree> stack = new Stack<BinaryTree>();
for (BinaryTree node = root; !stack.empty() || node != null; ) {
//寻找最左的左子树节点,并将遍历的左节点进栈
while(node!=null) {
stack.push(node);
node = node.getLeftChild();
}
if(!stack.empty()) {
node = stack.pop(); //出栈
node.visit(); //读取节点值
node = node.getRightChild();
}
}
}
}
//中序遍历的递归算法
public void inOrderRecursion (BinaryTree root) {
if(root!=null) {
inOrderRecursion(root.getLeftChild());
root.visit();
inOrderRecursion(root.getRightChild());
}
}
public static void main(String args[]) {BinaryTree node = new BinaryTree('A'); BinaryTree root = node; BinaryTree nodeL1; BinaryTree nodeL; BinaryTree nodeR; node.setLeftChild(new BinaryTree('B')); node.setRightChild(new BinaryTree('C')); nodeL1 = node.getLeftChild(); nodeL1.setLeftChild(new BinaryTree('D')); nodeL1.setRightChild(new BinaryTree('E')); nodeL = nodeL1.getLeftChild(); nodeL.setLeftChild(new BinaryTree('F')); node = node.getRightChild(); node.setLeftChild(new BinaryTree('G')); node.setRightChild(new BinaryTree('H')); nodeR = node.getLeftChild(); nodeR.setLeftChild(new BinaryTree('I')); nodeR.setRightChild(new BinaryTree('J')); VisitBinaryTree vt= new VisitBinaryTree(); //中序遍历递归和非递归测试vt.inOrder(root);vt.inOrderRecursion(root);}后序遍历：
//后序遍历非递归算法
private void postOrder(BinaryTree root) {
if(root!=null) {
Stack<BinaryTree> stack = new Stack<BinaryTree>();
for (BinaryTree node = root; !stack.empty() || node != null;) {
while(root!=null) {
stack.push(root);
root = root.getLeftChild();
}
while(!stack.empty() && root == stack.peek().getRightChild()) {
root = stack.pop();
root.visit();
}
if (stack.empty()) {
return;
} else {
root = stack.peek().getRightChild();
}
}
}
}
//后序遍历递归算法
private void postOrderRecursion(BinaryTree root) {
if(root!=null) {
postOrderRecursion(root.getLeftChild());
postOrderRecursion(root.getRightChild());
root.visit();
}
}
测试方法：
public static void main(String args[]) {
BinaryTree node = new BinaryTree('A');
BinaryTree root = node;
BinaryTree nodeL1;
BinaryTree nodeL;
BinaryTree nodeR;
node.setLeftChild(new BinaryTree('B'));
node.setRightChild(new BinaryTree('C'));
nodeL1 = node.getLeftChild();
nodeL1.setLeftChild(new BinaryTree('D'));
nodeL1.setRightChild(new BinaryTree('E'));
nodeL = nodeL1.getLeftChild();
nodeL.setLeftChild(new BinaryTree('F'));
node = node.getRightChild();
node.setLeftChild(new BinaryTree('G'));
node.setRightChild(new BinaryTree('H'));
nodeR = node.getLeftChild();
nodeR.setLeftChild(new BinaryTree('I'));
nodeR.setRightChild(new BinaryTree('J'));
VisitBinaryTree vt= new VisitBinaryTree();
//后序遍历递归和非递归测试
vt.postOrder(root);
vt.postOrderRecursion(root);
}