tree02.java

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

// =============== Program Description ===============
// 程序名称： tree02.java
// 程序目的： 依序输入元素值，以节点数组方式建立
//             二叉树，并输出节点内容。            
// Written By Kuo-Yu Huang. (WANT Studio.)            
// ===================================================
import ConsoleReader.*;					// 导入已定义的数据输入类

public class tree02
{
	public static void main (String args[])
	{
        	int i;					// 循环计数变量
        	int Index = 1;				// 数据索引变量
        	int Data;	            		// 读入输入值所使用的暂存变量
      		BNTreeArray BNTree = new BNTreeArray();	// 声明二叉树数组

		System.out.println("Please input the elements of binary tree(Exit for 0):");
     							
		ConsoleReader console = new ConsoleReader(System.in);

     		System.out.print("Data "+Index+" : ");
		Data = console.readInt();
		BNTree.TreeData[0] = Data;
		Index++;
		
     		while (true)				// 读取输入值
     		{
     			System.out.print("Data "+Index+" : ");
			Data = console.readInt();
			if ( Data == 0 )
				break;
 			BNTree.Create(Data);		// 建立二叉树
     			Index++;
		}

		BNTree.PrintAll();			// 输出二叉树的内容
	}
}

class BNTreeArray
{
	int MaxSize = 16;
	int[] TreeData = new int[MaxSize];
	int[] RightNode = new int[MaxSize];
	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]+"]");								
			}
		}
	}      
}