tree06.java

已经编写好的数据结构课本程序可以减轻您的负担

// =============== Program Description ===============
// 程序名称： tree06.java
// 程序目的： 输入欲查找的值，用折半查找方式进行
//             查找，最后输出查找结果
// Written By Kuo-Yu Huang. (WANT Studio.)            
// ===================================================
import ConsoleReader.*;					// 导入已定义的数据输入类

public class tree06
{
	public static void main (String args[])
	{		 
        	int i;					// 循环计数变量
        	int Data[] =				// 读入输入值所使用的暂存变量
        		{ 5, 2, 9, 4, 7, 3, 6, 8, 1,12};
      		BNTreeArray BNTree = new BNTreeArray();	// 声明二叉树数组
      		int KeyValue;				// 欲查找值

		BNTree.TreeData[0] = Data[0];
		
     		for ( i=1 ; i<10 ; i++)			// 读取输入值     		
 			BNTree.Create(Data[i]);		// 建立二叉树
 			
 		BNTree.PrintAll();			

		System.out.print("Please input the KeyValue for Binary Search : ");     							
		ConsoleReader console = new ConsoleReader(System.in);
		KeyValue = console.readInt();
		
		BNTree.BinarySearch(0,KeyValue);
		if ( BNTree.BinarySearch(0,KeyValue) > 0 )
		{
						// 输出查找次数
			System.out.println("");
			System.out.println("Search Time = "+BNTree.BinarySearch(0,KeyValue));
		}
		else
		{
						// 输出没有找到数据
			System.out.println("");
			System.out.println("No Found!!");
		}
	}
}

class BNTreeArray
{
	public static int MaxSize = 16;
	public static int[] TreeData = new int[MaxSize];
	public static int[] RightNode = new int[MaxSize];
	public static int[] LeftNode = new int[MaxSize];
	
	public BNTreeArray()
	{
		int i;					// 循环计数变量
		
		for ( i=0 ; i<MaxSize ; i++ )
		{
			TreeData[i] = 0;
			RightNode[i] = -1;
			LeftNode[i] = -1;
		}
	}

//----------------------------------------------------
// 建立二叉树
//----------------------------------------------------
	public void Create(int Data)
	{
      		int i;					// 循环计数变量
      		int Level = 0;				// 树的阶层数
      		int Position = 0;      		

		for ( i=0 ; TreeData[i] != 0 ; i++);
					
		TreeData[i] = Data;
		while ( true )			// 寻找节点位置
		{
	 						// 判断是左子树或是右子树
			if ( Data > TreeData[Level] )
			{
 	       						// 右树是否有下一阶层
				if ( RightNode[Level] != -1 )
	             			Level = RightNode[Level];
				else
				{
					Position = -1;	// 设定为右树
					break;
				}
			}
			else
			{
	        					// 左树是否有下一阶层
        	       		if ( LeftNode[Level] != -1 )
	             			Level = LeftNode[Level];
           	       		else
           	       		{
	             			Position = 1;	// 设定为左树
	             			break;
	             		}
                	}
                }
                
                if ( Position == 1)			// 建立节点的左右连接
	   		LeftNode[Level] = i;		// 连接左子树
                else
	   		RightNode[Level] = i;		// 连接右子树	
	}
	
//----------------------------------------------------
// 打印所有二叉树节点数据
//----------------------------------------------------
	public void PrintAll()
	{
      		int i;					// 循环计数变量
      		
		System.out.println("The Binary Tree Node Data : ");
		System.out.println("     [Left]  [Data]  [Right]");		
		
		for ( i=0 ; i<MaxSize ; i++ )
		{
			if ( TreeData[i] != 0 )
			{
				System.out.print("Node"+i);
				System.out.print("  ["+LeftNode[i]+"]");
				System.out.print("     ["+TreeData[i]+"]");
				System.out.println("     ["+RightNode[i]+"]");								
			}
		}
	}
	
//---------------------------------------------------------
// 二叉树折半查找方式
//---------------------------------------------------------
	public static int BinarySearch(int Root,int KeyValue)
	{
		int Counter = 1;
		int Pointer;
		
		Pointer = Root;
    		while ( Pointer != -1)
   		{
   							// 找到了欲寻找的节点
         		if ( TreeData[Pointer] == KeyValue )
              			return Counter;		// 传回查找次数
         		else if ( TreeData[Pointer] > KeyValue )          	
				Pointer = LeftNode[Pointer]; // 往左子树找
             		else
				Pointer = RightNode[Pointer];// 往右子树找
			Counter++;
   		}
   		return 0;				// 该节点不在此二叉树中
	}
}