tree07.java

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

// =============== Program Description ===============
// 程序名称： tree07.java
// 程序目的：输入一节点，并从二叉树中删除该节点。
// Written By Kuo-Yu Huang. (WANT Studio.)            
// ===================================================
import ConsoleReader.*;					// 导入已定义的数据输入类

public class tree07
{
	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;				// 欲查找值
      		int Pointer;

		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 Delete Node : ");
		ConsoleReader console = new ConsoleReader(System.in);
		KeyValue = console.readInt();
		
		BNTree.Delete(0,KeyValue);
		BNTree.PrintAll();
	}
}

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 static int Position = 0;		// 节点的位置(是左子树1或右子树-1)
	
	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;				// 树的阶层数

      		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 SearchParent(int Pointer,int Node)
	{
      		int Parent;				// 声明父节点的指针

      		Parent = Pointer;			// 设定指针初始值
      		Position = 0;				// 设定位置的初始值

      		while ( Pointer != -1 )
      		{
            		if ( TreeData[Pointer] == Node )// 找到该节点
            		{
				System.out.println("Parent"+Parent);
				System.out.println("Position"+Position);				
                 		return Parent;
                 	}
           		else
        		{
                		Parent = Pointer;	// 保留父节点指针
                		 			// 比较数据
				if ( TreeData[Pointer] > Node)
                		{
                					// 指向左子树
                      			Pointer = LeftNode[Pointer];
                      			Position = 1;	// 设定其为左子树
                		}
                		else
                		{
                			     		// 指向右子树
                       			Pointer = RightNode[Pointer];
                      			Position = -1;	// 设定其为右子树
        		        }
        		}
      		}
      		return -1;
	}
	
//---------------------------------------------------------
// 进行节点的删除
//---------------------------------------------------------
	public static void Delete(int Root,int Node)
	{
      		int Parent;				// 父节点指针
      		int Pointer = 0;			// 欲删除节点的指针
      		int Child;				// 子节点指针      		

     							// 寻找欲删除的节点的父节点指针
     		Parent = SearchParent(Root,Node);

 		if ( Parent != -1 )			// 该节点在二叉树中
 		{
           		switch ( Position )		// 判断删除的位置
           		{
                 		case 1:			// 左子节点
                 			Pointer = LeftNode[Parent];
         	             		break;
                 		case -1:		// 右子节点
                 			Pointer = RightNode[Parent];
   	             			break;
                 		case 0:			// 根节点
                 			Pointer = Parent;
            	             		break;
           		}
           		
       			// 没有左子树也没有右子树
        		if ( LeftNode[Pointer] == -1 && RightNode[Pointer] == -1 )
       			{
            			switch ( Position )	// 判断删除的位置
              			{
                 			case 1:		// 将父节点的左指针指向NULL
                 				LeftNode[Parent] = -1;
         	             			break;
                 			case -1:	//将父节点的右指针指向NULL*/
                 				RightNode[Parent] = -1;
   	             				break;
                 			case 0:		// 根节点指向NULL
                 				Parent = -1;
            	             			break;
               			}
       			}
        		// 没有左子树
          		if ( LeftNode[Pointer] == -1 && RightNode[Pointer] != -1 )
          		{				
          				// 将父节点的右指针指向节点的右子节点
                 		if ( Parent != Pointer )
                       			RightNode[Parent] = RightNode[Pointer];
                 		else	// 将根节点指向右子节点
                       			Root = RightNode[Root];
                 		Free(Pointer);		// 释放节点存储空间
          		}
           		// 没有右子树
         		else if ( RightNode[Pointer] == -1 && LeftNode[Pointer] != -1 )
          		{	
          				// 将父节点的左指针指向节点的左子节点
                 		if ( Parent != Pointer )        
                       			LeftNode[Parent] = LeftNode[Pointer];
                 		else	// 将根节点指向左子节点
                       			Root = LeftNode[Root];
                 		Free(Pointer);		// 释放节点存储空间
			}      
         		// 有左子树也有右子树
          		else if ( RightNode[Pointer] != -1 && LeftNode[Pointer] != -1)
          		{
               			Parent = Pointer;	// 将父节点指向目前的节点
               			Child = LeftNode[Pointer];// 设定子节点
               				// 找到左子树中的最右边的叶子点
               			while ( RightNode[Child] != -1 )
               			{
                    			Parent = Child;	// 保留父节点的指针
                    					// 往右子树前进
                    			Child = RightNode[Child];
               			}	// 将原节点设定成叶节点的数据值
               			TreeData[Pointer] = TreeData[Child];
               			if ( LeftNode[Parent] == Child )
		   			LeftNode[Parent] = LeftNode[Child];
              			else
                   			RightNode[Parent] = RightNode[Child];
              			Free(Child);		// 释放节点存储空间
          		}
  		}	
	}

//---------------------------------------------------------
// 节点的释放
//---------------------------------------------------------	
	public static void Free(int Pointer)
	{
		TreeData[Pointer] = 0;
		RightNode[Pointer] = -1;
		LeftNode[Pointer] = -1;		
	}
}