现在的位置: 首页 > 综合 > 正文

JAVA排序算法实现代码-二叉树排序

2013年08月15日 ⁄ 综合 ⁄ 共 4389字 ⁄ 字号 评论关闭
 

JAVA排序算法实现代码-二叉树排序

  1. /** 
  2.  * JAVA排序算法实现代码-二叉树排序。 
  3.  *  
  4.  * @author 老紫竹 JAVA世纪网(java2000.net) 
  5.  *  
  6.  */  
  7. public class Test {  
  8.   public static int[] a = { 01032195712243 }; // 预设数据数组  
  9.   public static int[] Data = new int[20]; // 预设数据数组  
  10.   
  11.   public static void main(String args[]) {  
  12.     int i; // 循环计数变量  
  13.     int Index = 1// 数据索引变量  
  14.     BNTreeArray BNTree = new BNTreeArray(); // 声明二叉树数组  
  15.   
  16.     Data[Index] = a[Index];  
  17.     BNTreeArray.TreeData[0] = Data[Index];  
  18.     Index++;  
  19.     for (i = 2; i < a.length; i++) {  
  20.       Data[Index] = a[Index];  
  21.       BNTree.Create(Data[Index]); // 建立二叉查找树  
  22.       Index++;  
  23.     }  
  24.   
  25.     // 排序前数据内容  
  26.     System.out.print("排序前 : ");  
  27.     for (i = 1; i < Index; i++)  
  28.       System.out.print(" " + Data[i] + " ");  
  29.     System.out.println("");  
  30.   
  31.     // 排序后结果  
  32.     System.out.print("排序后 : ");  
  33.     BNTreeArray.InOrder(0); // 中序遍历  
  34.   }  
  35. }  
  36.   
  37. class BNTreeArray {  
  38.   public static int MaxSize = 20;  
  39.   public static int[] TreeData = new int[MaxSize];  
  40.   public static int[] RightNode = new int[MaxSize];  
  41.   public static int[] LeftNode = new int[MaxSize];  
  42.   
  43.   public BNTreeArray() {  
  44.     int i; // 循环计数变量  
  45.   
  46.     for (i = 0; i < MaxSize; i++) {  
  47.       TreeData[i] = 0;  
  48.       RightNode[i] = -1;  
  49.       LeftNode[i] = -1;  
  50.     }  
  51.   }  
  52.   
  53.   // ----------------------------------------------------  
  54.   // 建立二叉树  
  55.   // ----------------------------------------------------  
  56.   public void Create(int Data) {  
  57.     int i; // 循环计数变量  
  58.     int Level = 0// 树的阶层数  
  59.     int Position = 0;  
  60.   
  61.     for (i = 0; TreeData[i] != 0; i++)  
  62.       ;  
  63.   
  64.     TreeData[i] = Data;  
  65.     while (true// 寻找节点位置  
  66.     {  
  67.       // 判断是左子树或是右子树  
  68.       if (Data > TreeData[Level]) {  
  69.         // 右树是否有下一阶层  
  70.         if (RightNode[Level] != -1)  
  71.           Level = RightNode[Level];  
  72.         else {  
  73.           Position = -1// 设定为右树  
  74.           break;  
  75.         }  
  76.       } else {  
  77.         // 左树是否有下一阶层  
  78.         if (LeftNode[Level] != -1)  
  79.           Level = LeftNode[Level];  
  80.         else {  
  81.           Position = 1// 设定为左树  
  82.           break;  
  83.         }  
  84.       }  
  85.     }  
  86.   
  87.     if (Position == 1// 建立节点的左右连结  
  88.       LeftNode[Level] = i; // 连结左子树  
  89.     else  
  90.       RightNode[Level] = i; // 连结右子树  
  91.   }  
  92.   
  93.   // ---------------------------------------------------------  
  94.   // 二叉树中序遍历  
  95.   // ---------------------------------------------------------  
  96.   public static void InOrder(int Pointer) {  
  97.     if (Pointer != -1// 遍历的终止条件  
  98.     {  
  99.       InOrder(LeftNode[Pointer]); // 处理左子树  
  100.       // 处理打印节点内容  
  101.       System.out.print(" " + TreeData[Pointer] + " ");  
  102.       InOrder(RightNode[Pointer]); // 处理右子树  
  103.     }  
  104.   }  
  105. }  

运行结果

排序前 : 10 32 1 9 5 7 12 2 4 3

排序后 : 1 2 3 4 5 7 9 10 12 32

抱歉!评论已关闭.