二叉树.txt

用 java实现的 搜索二叉树的插入、删除、遍历和平衡

import java.io.*;

class IntBSTNode{
       public int key;
       public IntBSTNode left,right;
        public IntBSTNode (){
            left=right=null;
                             }
        public IntBSTNode(int e1){
              this(e1,null,null);
                                  }
        public IntBSTNode(int e1,IntBSTNode lt,IntBSTNode rt){
                 key=e1;left=lt;right=rt;
                                                              }
         public void visit(){
           System.out.print(key + " ");
         }        
       }

class IntBST{int n=0;
          public IntBSTNode root;
          public IntBST(){
             root=null;
                          }

           public void insert(int el) {                  //插入
        IntBSTNode p = root, prev = null;
        while (p != null) {  // find a place for inserting new node;
            prev = p;
            if (p.key < el)
                 p = p.right;
            else p = p.left;
        }
        if (root == null)    // tree is empty;
             root = new IntBSTNode(el);
        else if (prev.key < el)
             prev.right = new IntBSTNode(el);
        else prev.left  = new IntBSTNode(el);
    }

    public void preorder(IntBSTNode p){                 //先序遍历
      if (p!=null){
          p.visit();
          preorder (p.left);
          preorder(p.right);
      }
    }
     public void inorder(IntBSTNode p) {               //中序遍历
         if (p != null) {
              inorder(p.left);
              p.visit();
              inorder(p.right);
         }
     }  
     protected void postorder(IntBSTNode p) {          //后序遍历
         if (p != null) { 
              postorder(p.left);
              postorder(p.right);
              p.visit();
         }
     }
     
     public void balance(int data[], int first, int last) {         //树的平衡
       if (first <= last) {
           int middle = (first + last)/2;
           insert(data[middle]);
           balance(data,first,middle-1);
           balance(data,middle+1,last);
       }
   }

      public void deleteByCopying(int el) {            //拷贝删除
           IntBSTNode node, p = root, prev = null;              
           while (p != null && p.key != el) {       // find the node p
                prev = p;                            // with element el;
                if (p.key < el)
                     p = p.right;
                else p = p.left;
           }
           node = p;
           if (p != null && p.key == el) {
                if (node.right == null)              // node has no right child;
                     node = node.left;
                else if (node.left == null)          // no left child for node;
                     node = node.right;
                else {
                     IntBSTNode tmp = node.left;     // node has both children;
                     IntBSTNode previous = node;     // 1.
                     while (tmp.right != null) {     // 2. find the rightmost
                         previous = tmp;             //    position in the
                         tmp = tmp.right;            //    left subtree of node;
                     }
                     node.key = tmp.key;             // 3. overwrite the reference
                     if (previous == node)           //    of the key being deleted;
                          previous.left  = tmp.left; // 4.
                     else previous.right = tmp.left; // 5.
                }
                if (p == root)
                     root = node;
                else if (prev.left == p)
                     prev.left = node;
                else prev.right = node;
           }
           else if (root != null)
                System.out.println("key " + el + " is not in the tree");
           else System.out.println("the tree is empty");
       }

   }
    public class Shu{
         public static void main(String []args)
       {IntBST tree=new IntBST();
         IntBST tree1=new IntBST();
        int i,x=0,n=0,u=0,v=0;
        int []b=new int[100];
     try{
      BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
      String s,input,cr,sc;
      System.out.print("请输入要建立树的节点个数：");
       input=in.readLine();
       x=Integer.parseInt(input);
      System.out.print("请输入要建立树的节点值：");
      for(i=0;i<x;i++)
     {
       s=in.readLine();
      n=Integer.parseInt(s);
      b[i]=n;
     tree.insert(n);
     }
      System.out.print("树的先序遍历为：");
      tree.preorder(tree.root); 
      System.out.println();
      System.out.print("树的中序遍历为：");
      tree.inorder(tree.root); 
      System.out.println();
      System.out.print("树的先后序遍历为：");
      tree.postorder(tree.root); 
      System.out.println();
      System.out.print("所建树变为平衡树的先序输出为：");
      tree1.balance(b,0,x-1);
      tree1.preorder(tree1.root); 
      System.out.println();
       System.out.print("如果要插入，请输入要插入的结点值："); 
       cr=in.readLine();
      u=Integer.parseInt(cr);
      tree.insert(u);
      System.out.print("此时树的先序遍历为：");
      tree.preorder(tree.root); 
      System.out.println();
      System.out.print("如果要删除，请输入要删除的结点值："); 
         sc=in.readLine();
        v=Integer.parseInt(sc);
        tree.deleteByCopying(v);
        System.out.print("此时树的先序遍历为：");
        tree.preorder(tree.root); 
        System.out.println();
}
        catch(Exception e){System.out.print(e);}
}
}