数据结构(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(