bitree.java

这是一个用java做的二叉树的遍历的实例！

import java.io.*;
import java.util.*;

	class TreeNode{//节点类
		public String data;//节点数据
		public TreeNode lchild,rchild;//左孩子及右孩子
		public TreeNode(String d){// 节点构造函数
			System.out.println("node created");//构造标志
			data = d; 
		}
		public TreeNode(){// 节点构造函数
			System.out.println("node created");
		}
		public void visitNode(){//输出节点数据
		System.out.print(data);
		}
	}
public class BiTree{
	public BiTree(){//主类构造函数
		TreeNode tn = new TreeNode();//建立新树根为空
		TreeNode tn2 = tn;
		tn.visitNode();
		System.out.println("start creating tree");//开始建树标志
		try{//建立二叉树
			createBiTree(tn);
		}catch(IOException e){
			e.printStackTrace();
		}
		outputTree(tn);//按层输出二叉树
	    }
	String instr;//接受输入的字符串变量
	String over = new String(" ");//结束符标志
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public TreeNode createBiTree(TreeNode tn1)throws IOException{//从键盘输入字符串，按先序次序输入并创建二叉树
		System.out.println("input node");
		try{//从键盘输入节点数据
			instr = br.readLine();
		}catch(IOException e){//捕获异常并输出异常信息
			e.printStackTrace();
		}
		if(instr.equals(over)){//如果为空则表示没有节点
			System.out.println("null node");
			tn1 = null;
		}
		else{//否则建立节点，并为该节点的左孩及右孩子建立节点如此循环
			tn1.data = instr;
			tn1.lchild = new TreeNode();
			tn1.lchild = createBiTree(tn1.lchild);
			tn1.rchild = new TreeNode();
			tn1.rchild = createBiTree(tn1.rchild);
		}
		return tn1;
	}
	public void outputTree(TreeNode tn){//二叉树按层输出，传入参数树根
		LinkedList ll = new LinkedList();//建立一个队列
		TreeNode tm = new TreeNode("newh");//新行标志
		int i = 0;
		if(tn!=null){
			ll.addLast(tm);//标志位入队尾
			ll.addLast(tn);//根入队列尾
		}
		while(ll.size() > 1){//如果栈里有元素，取第一个队列第一个元素并输出
			   TreeNode tn1 = (TreeNode)ll.getFirst();
			    if(tn1.data.equals("newh")){
					ll.removeFirst();
					System.out.println();
					System.out.print(++i);
					ll.addLast(tn1);
				}
				else{
					tn1.visitNode();//输出节点数据
					ll.removeFirst();//移出第一个元素
				}
				if(!(tn1.lchild==null)){//如果有左孩子，将其加入队列尾
					ll.addLast(tn1.lchild);
				}
				if(!(tn1.rchild==null)){
					ll.addLast(tn1.rchild);
				}
			}	
	}
	public void preOrder(TreeNode tn){
		if(!(tn==null)){
			tn.visitNode();
			preOrder(tn.lchild);
			preOrder(tn.rchild);
		}
	}
	public static void main(String args[]){//程序入口
		BiTree bt =new BiTree();
	}
}