treetest.java

本程序实现了二叉树遍历算法的递归和非递归实现。

public class TreeTest {
	public static void main(String args[]){
		BitTree bt=new BitTree();
		bt.toString(1);
		bt.toString(0);
	}
}

class BTstack{
	int top;
	Node2[] bs=null;
	BTstack(){   //体现一个思想：对象在使用时再初始化
		top=-1;
		bs=new Node2[20];   
	}
	
	void push(Node2 t)  /*进栈*/
	{ 
		bs[++top]=t;
	}
	Node2 pop()  /*出栈*/
	{
		if(top!=-1)
			return bs[top--];
		else
			return null;
	}
	void reset(){
		top=-1;
		bs=new Node2[20];   
	}
}


class BitTree { 
	public static Node2 root; 
	public static String asString; 

//	事先存入的数组,符号#表示二叉树结束。 
	public static final char[] treeLine = {'a','b','c','d','e','f','g',' ',' ','j',' ',' ','i','#'}; 

//	用于标志二叉树节点在数组中的存储位置，以便在创建二叉树时能够找到节点对应的数据。 
	static int index; 
	BTstack bts=new BTstack();

//	构造函数 
	public BitTree() { 
		System.out.print("测试二叉树的顺序表示为："); 
		System.out.println(treeLine); 
		this.index = 0; 
		root = this.setup(root); 
	} 

//	创建二叉树的递归程序 
	private Node2 setup(Node2 current) { 
		if (index >= treeLine.length) return current; 
		if (treeLine[index] == '#') return current; 
		if (treeLine[index] == ' ') return current; 
		current = new Node2(treeLine[index]); 
		index = index * 2 + 1; 
		current.left = setup(current.left); 
		index ++; 
		current.right = setup(current.right); 
		index = index / 2 - 1; 
		return current; 
	} 

//	二叉树是否为空。 
	public boolean isEmpty() { 
		if (root == null) return true; 
		return false; 
	} 

//	返回遍历二叉树所得到的字符串。 
	public String toString(int type) { 
		if (type == 0) { 
			asString = "前序遍历：\t"; 
			this.front(root); 
		} 
		if (type == 1) { 
			asString = "中序遍历：\t"; 
			this.middle(root); 
		} 
		if (type == 2) { 
			asString = "后序遍历：\t"; 
			this.rear(root); 
		}
		return asString; 
	} 

//	前序遍历二叉树的循环算法，每到一个结点先输出，再压栈，然后访问它的左子树， 
/*//	出栈，访问其右子树，然后该次循环结束。 */
	private void front(Node2 current) { 		
/*方法一: 递归调用
        if (current == null) return; 		 
		asString += current.ch; 
		System.out.println(asString);
		front(current.left);
		front(current.right); */
/*方法二: 非递归方式——把右节点压栈*/		
		if (current == null) return; 
	    while(current!=null){
		  while(current!=null){			//处理某颗子树的左子树
			System.out.println(asString += current.ch);
			if(current.right!=null)
				bts.push(current.right);
			current=current.left;           //准备新的子树
		  }
		  if(bts.top!=-1){                  //准备某颗子树的右子树
			current=bts.pop();			
		  }
	    }
		bts.reset();		
/*方法三: 非递归方式——把根节点压栈
		Stack stack = new Stack ((Object)current); 
		do { 
			if (current == null) { 
				current = (Node2)stack.pop(); 
				current = current.right; 
			} else { 
				asString += current.ch; 
				current = current.left; 
			} 
			if (!(current == null)) stack.push((Object)current); 
		} while (!(stack.isEmpty())); */
	}
	
//	中序遍历二叉树 
	private void middle(Node2 current) { 
		/*方法一: 递归方式*/
/*		if (current == null) return; 
		middle(current.left); 
		asString += current.ch; 
		System.out.println(asString);
		middle(current.right); */
		/*方法二: 非递归方式——把右节点压栈*/		
		if (current == null) return; 
	    do{
		  while(current!=null){			//处理某颗子树
			//System.out.println(asString += current.ch);
			bts.push(current);
			current=current.left;           //子树
		  }
		  if(bts.top!=-1){                  //准备栈中的某颗子树
			  current=bts.pop();
			  System.out.println(asString += current.ch);
			  current=current.right;						
		  }
	    }while(current!=null||bts.top!=-1);
		bts.reset();
	} 

//	后序遍历二叉树的递归算法 
	private void rear(Node2 current) { 
		if (current == null) return; 
		rear(current.left); 
		rear(current.right); 
		asString += current.ch; 
	} 
} 


	/** 
	* 二叉树所使用的节点类。包括一个值域两个链域 
	*/ 

class Node2 { 
	char ch; 
	Node2 left; 
	Node2 right; 

//	构造函数 
	public Node2(char c) { 
		this.ch = c; 
		this.left = null; 
		this.right = null; 
	} 

//	设置节点的值 
	public void setChar(char c) { 
		this.ch = c; 
	} 

//	返回节点的值 
	public char getChar() { 
		return ch; 
	} 

//	设置节点的左孩子 
	public void setLeft(Node2 left) { 
		this.left = left; 
	} 

//	设置节点的右孩子 
	public void setRight (Node2 right) { 
		this.right = right; 
	} 

//	如果是叶节点返回true 
	public boolean isLeaf() { 
		if ((this.left == null) && (this.right == null)) return true; 
		return false; 
	} 
}