bst.java

实现ADT,可以实现两个二叉树的几种逻辑关系来显示它们之间的联系.如:求两个二叉树是否是等价的.它们的交集并集是怎样的.等等.这样这些都是ADT要实现的方法.

import javax.swing.JOptionPane;
public class BST {

// Inner class
    public static int sz;//定义整形的结点数
    public static class Node {    //该类是BST的私有成员
    public Comparable data;//比较型的值,用来存结点的值  
    public Node left;//定义了左右子树                                     
    public Node right;
    

   public Node() { this(null, null, null); }

    public Node(Comparable obj) { this(obj, null, null); }//构造函数

   public Node(Comparable obj, Node leftChild, Node rightChild) {
      data = obj; 
      left = leftChild; 
      right = rightChild;
     // sz=0;
    }

    public String toString()//显示二叉树
    { return data.toString(); }//调用重载函数
  }//结束该类

  // Each BST object is (a header of) a binary search tree (BST).
  // This BST is represented simply by a reference to its root node (root).
 public static Node root; 
 public static Node root1;     //root node of the tree   
// Constructor
  public BST() { root = null; }
  
// Modifiers
  public static void clear() { root = null;sz=0; } //清空函数结点值也赋值为零
  public static void insert (Comparable val)//插入函数调用重载函数           
  { root = insert(root, val); sz=sz+1;}//这时插入一个结点,结点数值加一
  public static void insert1 (Comparable val)
  { root1 = insert(root1, val); }//给另一个二叉树插值
    
  public static void delete (Comparable val)//调用重载函数删除结点
  { root = delete(root, val); }
    
// Accessors
  public static boolean contains (Comparable val)////////
  {	return search(root, val) != null; }
  
 public static void union (){//并集
 String ss="",sss="";//两个二叉树的输入用这两个字符串来做为输入
 clear();//将root清空将用来装并集的二叉树                     
 while(true){//输入第一个二叉树         
  ss=JOptionPane.showInputDialog( "输入第一个二叉树的值输入 'over' 退出 :" );   
  if(ss.compareTo("over")!=0)//直到输入是"over"时结束                      
  insert(Integer.valueOf(ss));//将第一个二叉树的值插入到root二叉树
  else
   break;
 }
 while(true){
 
  sss=JOptionPane.showInputDialog( " 输入第二个二叉树的值输入 'over' 退出 : :" );  
  //第二个二叉树的输入                                                               
  if(sss.compareTo("over")!=0)//输入是"over"时,结束
   insert(Integer.valueOf(sss));//将第二个二叉树的值插入root二叉树
  else
   break;
 }
}
public static void intersection (){//完成交集
	clear();//将用来显示交集的root二叉树清空   
String s1="",s2="";
String Y1[]=new String[100];//用整形的数组来保存二叉树的结点值
String Y2[]=new String[100];
String Y[]=new String[100];
for(int y=0;y<100;y++)
Y1[y]=" ";
int i=0,j=0,j1=0;
 while(true){//接收第一个二叉树的结点值
  s1=JOptionPane.showInputDialog( "输入第一个二叉树的值输入 'over' 退出  :" );   
  if(s1.compareTo("over")!=0)
  {
  	Y1[i]=s1;//将结点值保存到数组
  	i++;
  }
  else{   
   break;}
 }
while(true){
  s2=JOptionPane.showInputDialog( "输入第二个二叉树的值输入 'over' 退出  :" );  
  //接收第二个二叉树的结点值                                                      
  if(s2.compareTo("over")!=0)
  { 
   for(int i1=0;i1<Y1.length;i1++)
   if(s2.compareTo(Y1[i1])==0)//当与第一个二叉树的值相等时
   { 
   insert(Integer.valueOf(s2));//将相等的值的结点插入到root的二叉树中
     break;
   }
 }
 else{
   break;}
 }	 	
}
public static boolean equals (){//完成等价
 String s;
 Comparable val;
  s=JOptionPane.showInputDialog( "输入要比较的二叉树的值输入 'over' 退出  :"); 
  root1=null;//将root1定义为要比较的二叉树                                     
  while(s.compareTo("over")!=0)
  { 
    val=Integer.valueOf(s);
  	insert1 (val);//当没有结束时将值插入root1
  	s=JOptionPane.showInputDialog( "输入要比较的二叉树的值输入 'over' 退出  :"); 
  }
  print(root1,0);
  if(equals(root,root1)==true)//调用重载的等价方法返回是真时
  return true;//就返回真表示是等价的二叉树                     
  return false;
}
  public static void print()  //显示二叉树的方法
  { print(root, 0); }

// Auxiliary method
  public static Node insert (Node ptr, Comparable val) {//重载的插入方法
  // Insert the element elem in this BST.
    if (ptr == null) 
      return new Node(val);
    else {
      int comp = val.compareTo(ptr.data);
      if (comp < 0)//比当前结点值小时     
        ptr.left = insert(ptr.left, val);//就插入到左子树
      else  // comp >= 0否则
        ptr.right = insert(ptr.right, val);//插入到右二叉树
      return ptr;  	   	
    }
  }

  public static Node delete (Node ptr, Comparable val) {//重载的删除方法
  // Delete the element elem in this BST. 
    if (ptr == null) return null;
    else {
      int comp = val.compareTo(ptr.data);
      if (comp == 0)//找到了要删除的结点                      
       {sz=sz-1;//结点值减少1            
        return deleteTopmost(ptr);}
      else if (comp < 0)//比当前结点小就到左二叉树删除结点
        ptr.left = delete(ptr.left, val);
      else  // comp > 0否则
        ptr.right = delete(ptr.right, val);//到右二叉树删除结点
      return ptr;
    } 
  }
    
 public static Node deleteTopmost (Node ptr) {//删除结点后的二叉树
    if (ptr.left == null)//当任意子树是空就返回另一个子树           
      return ptr.right;
    else if (ptr.right == null)
      return ptr.left;
    else {  // this node has both a left child and a right child否则
      ptr.data = getLeftmost(ptr.right);
      //将要删掉的结点的值覆盖，用右子树的最下最左的叶结点代替
      ptr.right = deleteLeftmost(ptr.right);//右子树也要被新子树覆盖                          
      return ptr;
    }
  }
  
  public static Comparable getLeftmost (Node ptr) {//返回地是最左最下地叶结点
  // Return the element in the leftmost node of the (nonempty) subtree
  // whose topmost node is this.
    if (ptr.left == null)  
      return ptr.data;
    else return getLeftmost(ptr.left);
  }
    
 public static Node deleteLeftmost (Node ptr) {//巧妙地将新右子树返回
  // Delete the leftmost node of the (nonempty) subtree
  // whose topmost node is this.
  // Return a link to the modified subtree.
    if (ptr.left == null) return ptr.right;
    //当右子树只有一层，则左叶结点已作为了删掉的结点    
    else {
      ptr.left = deleteLeftmost(ptr.left);
      return ptr;
    }
  }
    
  public static Node search (Node ptr, Comparable val) {//与删除方法相似
    if (ptr == null) return null; 
    else {      
      int comp = val.compareTo(ptr.data);
      if (comp == 0)
        return ptr;
      else if (comp < 0)
        return search(ptr.left, val);
      else
        return search(ptr.right, val);
    }
  }
public static boolean isEmpty (){//完成检查是否空
  	if(root==null)
  	return true;
  	return false;
}
public  static int size (){   //完成结点数
	return sz;
}
public static boolean equals (Node ptr,Node pr){//完成等价的重载方法
if(ptr==null&&pr==null)
return true;//都是空则是等价的
if(ptr==null)//否则只有一个是空时就是不等价的
return false;
if(pr==null)
return false;
int es=(ptr.data).compareTo(pr.data);//都不是空时比较当前结点
if(es!=0)//结点值不同就是不等价的                              
return false;
//相等时做下一步,不然已返回了false
if(equals(ptr.left,pr.left)!=false&&equals(ptr.right,pr.right)!=false)
//接着比较子树的结点 是相等时                                                                                               
return true;
else
return false;
}     
public static boolean subset(){//完成是否是子树

String s;
 Comparable val;
  s=JOptionPane.showInputDialog( "输入子二叉树的值输入 'over' 退出  :"); 
  root1=null;
  while(s.compareTo("over")!=0)
  { 
    val=Integer.valueOf(s);
  	insert1 (val);
  	s=JOptionPane.showInputDialog( "输入子二叉树的值输入 'over' 退出  :"); 
  }//建立一个子二叉树                                                        
  print(root1,0);//显示要比较的子二叉树
  if(root1==null)//任意二叉树都有空子树
  return true;
  
  Node s1=search (root, root1.data);//首先找到子树的当前结点
  if(s1==null)//没有找到时                                   
  return false;//即没有该子树
  if(equals(s1,root1)==true)//找到,继续比较以这两个当前结点做为根的子二叉树
  return true;//如果两个子树是等价的,则二叉树含有这个子二叉树               
  return false;

}
  public static void print (Node ptr, int level) {//将二叉树逆时针旋转90度显示出来
    if (ptr == null) return;
    print(ptr.right, level+1);
    for (int i=0; i<level; i++)//用level来控制要空的格数来区别不同的深度的结点
    System.out.print("    ");
    System.out.println(ptr.data);//最先显示的必然是最深最右的结点
    print(ptr.left, level+1);//最后显示的则是最深最左的结点       
  }
}