tree05.java

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

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

public class tree05
{
	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++;
		}
       		System.out.print("The Postorder Traversal result is [ ");
       		BNTree.PostOrder(0);			// 后序遍历
       		System.out.println("]");
	}
}

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 static void PostOrder(int Pointer)
	{
      		if ( Pointer != -1)			// 遍历的终止条件
     		{
			PostOrder(LeftNode[Pointer]);	// 处理左子树     			
			PostOrder(RightNode[Pointer]);	// 处理右子树
     							// 处理打印节点内容
        		System.out.print(" "+TreeData[Pointer]+" ");			
     		}
	}
}