package com.soke.demo7;
import java.util.Date;
public class Sort {
/**
  * 作者：麦子
  * 功能：实现各种排序算法：二叉树排序
  * 本文中所采用的数据结构和算法都是个人思路,可能您有更好的数据结构和算法
  * 如有疑问和指教，请E-mail：89104774@qq.com
  */
public static void main(String[] args) {
  int len=100000;
  int[] arrf=new int[len];int[] arrg=new int[len];
  for(int i=0;i<len;i++){
   int t=(int)(Math.random()*100);
  arrf=t;
  }
/* for(int i=0;i<arr.length;i++){
   System.out.print(arr+" ");
  }
  System.out.println();     */
  
  //多态的体现,都可以用一个sort对象的sort方法来处理,jvm可自行解析是哪一个对象的sort方法
/*  Sort sort = new BinaryTree();
  sort.sort(arra);   */
/*  Sort sort = new Merger();
  sort.sort(arra);   */
  
  Sort sort6 = new BinaryTree();
  Date date10 = new Date();
  long a10 = date10.getTime();
  sort6.sort(arrf);
  Date date11 = new Date();
  long a11 = date11.getTime();
  System.out.println("二叉树排序用时:"+(a11-a10)+"毫秒");  

  
/* 本程序中如果子类中没有重载或重写打印方法时，便都可采用下面的for循环来打印，
  *  由于采用的是引用传递，故arr中元素的顺序已然发生变化
  *  特别注意当上面的 len 较大时，就不要打印了，这个相当耗时
     sort.show();
     sort.traverseBinaryTree();
  for(int i=0;i<arr.length;i++){
   System.out.print(arr+" ");
  }   */
}

//下面的空方法，是为了实现java语言三大特征之一的多态，多态与继承联系甚为紧密
public void sort(int arr[]){}
public void traverseBinaryTree(){}
public void sort(int arr[],int low,int high){}
public void show(){}
}

//******************************************************************************
/*二叉树排序用的是二叉排序树的原理,二叉树排序书：即将某个结点为'根结点',其左子树
* 中的元素均小于或等于’根结点‘元素,其右子树中所谓所谓的元素均大于’根结点元素‘.将数组中
* 的所有元素依次插入二叉排序树中,然后中序遍历整棵二叉排序树就为排好序的数列,若存储结构才有二叉树
* 本算法思想：创建一个结点类,将结点共有的属性(data、Lchild、Rchild、Parent)抽象出来作为结点类的成员属性.
* 创建一个二叉排序树的类,将二叉排序树共有的属性(totalNode、RootNode)抽象出来作为二叉排序树类的成员属性.
* 将二叉排序树共有的方法(sort、traverseBinaryTree)抽象出来作为二叉排序树类的成员方法.二叉排序树的sort方法
* 实为一个将数组元素依次插入二叉排序树中的一个过程,将数组的第一个元素作为二叉排序树的根结点,然后将数组
* 第一个元素之后的所有元素依次插入这棵二叉排序树中.二叉排序树的traverseBinaryTree方法即为中序遍历已经建好
* 二叉排序树,这里我偷个懒采用了一种简单思路来遍历,就是找根结点的左孩子,然后又找这个左孩子结点的左孩子......
* 直至这个左孩子结点没有左孩子没有左孩子时,那么这个元素即为整个二叉排序中最小的元素,为什么是这样请仔细品味
* 二叉排序树的原理,这里就不再赘余了.
*/
//创建一个结点类，类属性包括：结点的数据、结点的左指针、结点的右指针
class Node{
int data = 0;//数据域的值
Node Lchild = null;//指向左孩子的指针
Node Rchild = null;//指向右孩子的指针
Node Parent = null;//指向其双亲结点的指针;
}
//创建一个二叉排序树类,让其继承父类sort
class BinaryTree extends Sort{
int totalNode = 0;
Node RootNode = new Node();//根结点
Node temp = new Node();
//初始化二叉排序树
/* public void creatBinaryTree(int arr[]){//创建一个二叉排序树           */
public void sort(int arr[]){//创建一个二叉排序树
  totalNode = arr.length;
  RootNode.data = arr[0];//将根节点的数据域指向数组的第一个元素坐在的地址
  for(int i=1;i<arr.length;i++){//控制循环次数，即向二叉排序树中插入结点的个数
   temp.Parent = RootNode;
   Node node = new Node();
   while((arr<=temp.Parent.data&&temp.Parent.Lchild!=null)||
     (arr>temp.Parent.data&&temp.Parent.Rchild!=null))
   {    while(arr<=temp.Parent.data&&temp.Parent.Lchild!=null){
        temp.Parent = temp.Parent.Lchild;
       }
       while(arr>temp.Parent.data&&temp.Parent.Rchild!=null){
        temp.Parent = temp.Parent.Rchild;
       }
   }
   if(arr<=temp.Parent.data){
    temp.Parent.Lchild = node;
    node.Parent = temp.Parent;
    node.data = arr;
   }else{
    temp.Parent.Rchild = node;
    node.Parent = temp.Parent;
    node.data = arr;
   }
  }
}
public void traverseBinaryTree(){//中序遍历二叉排序树的方法
  for(int i=0;i<totalNode;){
   //每次都将temp节点的父指针指向根结点，并向下寻找结点data值最小的元素
   temp.Parent = RootNode;
   if(temp.Parent.Lchild!=null){//如果根结点有左孩子
    while(temp.Parent.Lchild!=null){
     temp.Parent = temp.Parent.Lchild;
    }//推出循环时，temp的parent指针指向的结点的data元素即是最小的
    System.out.print(temp.Parent.data+" ");
    i++;//打印一次date就将i自加
   //temp的parent指针指向的结点的date打印 完后，就将该结点从树中删除
   //删除这个结点的同时也要把断了的结点连起来
    if(temp.Parent.Lchild==null&&temp.Parent.Rchild==null){
     temp.Parent.Parent.Lchild = null;
     temp.Parent.Parent = null;
    }
    else if(temp.Parent.Lchild==null&&temp.Parent.Rchild!=null){
     temp.Parent.Parent.Lchild = temp.Parent.Rchild;
     temp.Parent.Rchild.Parent = temp.Parent.Parent;
    }
   }else{//如果根结点没有左孩子
    if(temp.Parent.Rchild!=null)
    {
     System.out.print(temp.Parent.data+" ");
     i++;
     RootNode = temp.Parent.Rchild;
     temp.Parent.Rchild.Parent = null;
     temp.Parent.Rchild = null;
    }else{
     System.out.print(temp.Parent.data+" ");
     i++;
    }
   }
  }
}
}

//****************************附上某次测试时的结果******************************

//二叉树排序用时:1156毫秒

//******************************************************************************

值得学习ing!