queue.java~22~

av平衡树

/**
 * <p>Title: </p>
 *
 * <p>Description: </p>
 *
 * <p>Copyright: Copyright (c) 2006</p>
 *
 * <p>Company: </p>
 *
 * @author not attributable
 * @version 1.0
 */
public class Queue {
    LinkList ls;
    public Queue() {
        ls=new LinkList() ;
    }
    public void add(ATNode da){
       // System.out.println(Double.toString(da.data)) ;
       ls.addANodeToEnd(da) ;
    }
    public ATNode delete(){
        return ls.deleteHeadNode() ;
    }
    public boolean isEmpty(){
    return ls.isEmpty() ;
}
//public double head(){
        //return ls.getHead() ;
      //     }
public boolean isFull(){
    try{
        Node n = new Node();
        return false;
    }catch(Exception e){return true;}
}
public void show(){
    System.out.println(ls.getList() ) ;
}
public static void main (String[]as){
    ATree a = new ATree();
       try{System.out.println( a.High()) ;
           a.Insert(1);//System.out.println( a.High()) ;
           //a.Ascend() ;
          a.Insert(2);//System.out.println( a.High()) ;
          // a.Ascend() ;
          a.Insert(6);//System.out.println( a.High()) ;
          // a.Ascend() ;
          a.Insert(4);
         // a.Ascend() ;
         a.Insert(5);
          // a.Ascend() ;
           a.Delete(1) ;a.Ascend() ;
         //  a.Delete(1) ;a.Ascend() ;
           a.Insert(1);
           a.Ascend() ;
           ATNode an=a.root,an1 ;
           Queue qu=new Queue() ;
           qu.add(an);
           while(!qu.isEmpty() ){
               an=qu.delete() ;
               if(an.LeftChild !=null){
                   an1 = an.LeftChild;
                   qu.add(an1);
                   qu.show();
               }
               if(an.RightChild !=null){
                   an1=an.RightChild ;
                   qu.add(an1);
                   qu.show();
               }
           }
           an=new ATNode(3) ;
           qu.add(an) ;
           qu.show() ;
       }catch(Exception e){}

}
}

class LinkList {
      private Node head;
      public Node last;

    public LinkList()
    {
        head=last = null;
    }
   public ATNode getHead(){
       if(head==null)
           return null;
       else return head.data ;
   }
   public ATNode getLast(){
       if(last==null)
           return null;
       else return last.data ;
   }

      public void addANodeToStart(ATNode data)
    {
        head = new Node(data,head);
    }
    public void addANodeToEnd(ATNode data)
     {
        Node  nd= new Node(data);
        if(last==null)
            head=last=nd;
        else{//System.out.println(Double.toString(data.data)) ;
            last.rLink = nd;
            last = nd;
        }
      //  System.out.println(getList()); System.out.println(Double.toString(data.data)) ;
    }
    public  ATNode deleteHeadNode()
    {ATNode d=null;
        if (head != null)
        {d=head.data;
            head = head.rLink;

        }
        else
        {
            System.out.println("Deleting from an empty list.");

        }
        return d;
    }
    public boolean isEmpty(){
       return head==null;
   }


    public String getList(){
      String st="";int i=0;
      Node position;
       position = head;
       while (position != null)
       {i++;
         if(i%9==0)
          st=st+"   "+Double.toString((position.data).data )+"\n";
          else st=st+"   "+Double.toString((position.data).data );
           position = position.rLink;
       }
    return st;
    }



    public void add(LinkList list){
        Node position;
          position = head;
          if(position==null)
            head=list.head ;
          while (position != null)
          {
              if(position.rLink==null){
                position.rLink = list.head;
                break;
              }
              position = position.rLink;
          }
    }

  }
  class Node {

      public Node rLink;
      public ATNode data;
      public Node() {

        rLink=null;
        data=null;
      }
      public Node (ATNode data){this.data =data;}
      public Node (ATNode data ,Node rlink){this.data =data ;rLink =rlink;}

  }