java二叉树的遍历(递归和非递归).doc

import java.util.Stack;
public class MyTree{
public static void main(String[] s){
new MyTree();
}
public MyTree(){
TreeNode root = init();//初始化二叉树并返回根节点
System.out.println("递归先序遍历");
preorder(root);
System.out.println();
System.out.println("递归中序遍历");
inorder(root);
System.out.println();
System.out.println("递归后续遍历");
posorder(root);
System.out.println();
System.out.println("非递归先序遍历");
preorder(root);
System.out.println();
System.out.println("非递归中序遍历");
_inorder(root);
System.out.println();
System.out.println("非递归后续遍历");
_posorder(root);
System.out.println();
}
public void preorder(TreeNode root){//递归二叉树的前序遍历
if(root != null){
System.out.print(root.getValue());//访问节点值
preorder(root.getLeft());
preorder(root.getRight());
}
}
public void _preorder(TreeNode root){//非递归二叉树的前序遍历
Stack<TreeNode> stack = new Stack<TreeNode>();//定义堆栈存储
while(!(root == null && stack.isEmpty())){
System.out.print(root.getValue());//访问节点
if(root != null){//找到当前节点最深的左子树
stack.push(root);//将当前左子树入栈
root = root.getLeft();
}else{//当左子树到底时，开始访问右节点
root = stack.pop();//当前节点出栈
root = root.getRight();//指向右子树
}
}
}
public void inorder(TreeNode root){//递归中序遍历
if(root != null){
inorder(root.getLeft());
System.out.print(root.getValue());
inorder(root.getRight());
}
}
public void _inorder(TreeNode root){//非递归中序遍历
Stack<TreeNode> stack = new Stack<TreeNode>();
while(!(root == null && stack.isEmpty())){
while(root != null){//先找到最深的左子树
stack.push(root);
root = root.getLeft();
}
//找到最深左子树后开始访问
root = stack.pop();
System.out.print(root.getValue());
//开始寻找右子树
root = root.getRight();
}
}
public void posorder(TreeNode root){//递归后序遍历
if(root != null){
posorder(root.getLeft());
posorder(root.getRight());
System.out.print(root.getValue());
}
}
//非递归的后续遍历需要两次访问节点，最后一次访问节点为准
private int sign = 0;//得当当前访问节点的次数
public void _posorder(TreeNode root){
Stack stack = new Stack();//定义一个可以存放TreeNode 和 Integer的栈
while(!(root == null && stack.isEmpty())){
if(root != null){//找最深左子树
stack.push(root);//将当前节点压入堆栈
stack.push(1);//并标记当前访问节点的次数
root = root.getLeft();
}else{//找到最深左子树后
while(!stack.isEmpty()){
sign = (Integer)stack.pop();//出栈标记
root = (TreeNode)stack.pop();//出栈节点
if(sign == 1){//地一次访问节点
stack.push(root);
stack.push(2);
root = root.getRight();//将节点指向右子树并开始访问指向右子树的左子树
break;
}else if(sign == 2){//当第二次出栈时访问节点
System.out.print(root.getValue());
root = null;
}
}
}
}
}
public TreeNode init(){//二叉树的初始化
TreeNode e = new TreeNode('E');//叶子节点
TreeNode f = new TreeNode('F');
TreeNode d = new TreeNode('D',e,f);//带有左右子树的节点
TreeNode c = new TreeNode('C');
TreeNode b = new TreeNode('B',c,d);
TreeNode j = new TreeNode('J');
TreeNode h = new TreeNode('H',null,j);//带有右子树的节点
TreeNode i = new TreeNode('I');
TreeNode g = new TreeNode('G',h,i);
TreeNode a = new TreeNode('A',b,g);
return a;
}
}
//建立二叉树的节点类
class TreeNode{
public char data;
public TreeNode left,right;
public TreeNode(char data){
this(data,null,null);
}
public TreeNode(char data,TreeNode left,TreeNode right){
this.data = data;
this.left = left;
this.right = right;
}
public TreeNode getLeft(){//返回左子树
return left;
}
public TreeNode getRight(){//返回右子树
return right;
}
public char getValue(){//访问节点值
return data;
}
}