public class TreeIndex{
	public static void printBiTree(BiTreeNode root, int level){
	//二叉樹root第level層結(jié)點(diǎn)數(shù)據(jù)元素值的橫向輸出
		if(root != null){
			//子二叉樹root.getRight()第level+1層結(jié)點(diǎn)數(shù)據(jù)元素值的橫向輸出
			printBiTree(root.getRight(),level + 1);

			if(level != 0){
				//走過6*(level-1)個(gè)空格
				for(int i = 0; i < 6 * (level - 1); i ++){
					System.out.print(" ");
				}
				System.out.print("---");		//輸出橫線
			}
			System.out.println(root.data); 		//輸出結(jié)點(diǎn)的數(shù)據(jù)元素值

			//子二叉樹root.getLeft()第level+1層結(jié)點(diǎn)數(shù)據(jù)元素值的橫向輸出
			printBiTree(root.getLeft(),level + 1);
		}
	}
	
	public static BiTreeNode search(BiTreeNode t, Object x){
		BiTreeNode temp;
	
		if(t == null) return null; 					//查找失敗出口
		if(t.data.equals(x)) return t; 				//查找成功出口
	
		if(t.getLeft() != null){
			temp = search(t.getLeft(),x); 			//在左子樹查找
			if(temp != null) return temp; 			//查找成功則結(jié)束遞歸
		}
	
		if(t.getRight() != null){
			temp = search(t.getRight(),x); 			//在右子樹查找
			if(temp != null) return temp; 			//查找成功則結(jié)束遞歸
		}
		
		return null; 								//查找失敗出口
	}

	
	public static BiTreeNode getTreeNode(Object item, BiTreeNode left, BiTreeNode right){
		BiTreeNode temp = new BiTreeNode(item,left,right);
		return temp;
	}

	public static BiTreeNode makeTree(){
		BiTreeNode b, c, d, e, f, g;
		
		g = getTreeNode(new Character('G'), null, null);
		d = getTreeNode(new Character('D'), null, g);
		b = getTreeNode(new Character('B'), d, null);
		e = getTreeNode(new Character('E'), null, null);
		f = getTreeNode(new Character('F'), null, null);
		c = getTreeNode(new Character('C'), e, f);
		return getTreeNode(new Character('A'), b, c);
	}
	
	public static void main(String[] args){
		BiTreeNode root1;
		BiTreeNode temp;
		Visit vs = new Visit();						//創(chuàng)建Visit類對象vs
		
		root1 = makeTree();
		System.out.println("二叉樹為：");
		printBiTree(root1,0);
		System.out.println();
		
		System.out.print("前序遍歷結(jié)點(diǎn)序列為：");
		Traverse.preOrder(root1,vs);
		System.out.println();
		
		System.out.print("中序遍歷結(jié)點(diǎn)序列為：");
		Traverse.inOrder(root1,vs);
		System.out.println();
		
		System.out.print("后序遍歷結(jié)點(diǎn)序列為：");
		Traverse.postOrder(root1,vs);
		System.out.println();
		
		System.out.print("層序遍歷結(jié)點(diǎn)序列為：");
		try{
			Traverse.levelOrder(root1,vs);
		}
		catch(Exception e){
			e.printStackTrace();
		}
		System.out.println();
		
		temp = search(root1,new Character('C'));
		if(temp != null)
			System.out.println("查找到的結(jié)點(diǎn)數(shù)據(jù)值為：" + temp.data);
		else
			System.out.println("查找失敗");
	}
}