BSTree.java

//Binarno iskalno drevo
 
public class BSTree implements Dictionary {
  BSTreeNode rootNode;
 
  public BSTree() {
   makenull() ;
  }
 
  public void makenull() {
    rootNode = null;
  }
 
  public boolean member(Object x) {
    return member((Comparable) x, rootNode) ;
  }
 
  private boolean member(Comparable x, BSTreeNode node) {
    if (node == null)
      return false;
    else if (x.compareTo(node.key) == 0)
      return true;
    else if (x.compareTo(node.key) < 0)
      return member(x, node.left);
    else
      return member(x, node.right);
  }
 
  public void insert(Object x) {
    rootNode = insertLeaf((Comparable)x, rootNode);
    // alternatively:   rootNode = insertRoot((Comparable)x, rootNode);
  }
 
  protected BSTreeNode insertLeaf(Comparable x, BSTreeNode node) {
    if (node == null)
      node = new BSTreeNode(x);
    else if (x.compareTo(node.key) < 0)
      node.left = insertLeaf(x, node.left);
    else if (x.compareTo(node.key) > 0)
      node.right = insertLeaf(x, node.right);
    else
      ; // duplicate; do nothing
    return node;
  }
 
  public void insertRoot(Comparable x) {
    rootNode = insertRoot(x, rootNode);
  }
 
  private BSTreeNode insertRoot(Comparable x, BSTreeNode node) {
    if (node == null)
      node = new BSTreeNode(x);
    else if (x.compareTo(node.key) < 0) {
      node.left = insertRoot(x, node.left);
      node = rightRotation(node);
    }
    else if (x.compareTo(node.key) > 0) {
      node.right = insertRoot(x, node.right);
      node = leftRotation(node);
    }
    else
      ; // duplicate; do nothing
    return node;
  }
 
  protected BSTreeNode rightRotation(BSTreeNode node) {
    BSTreeNode temp = node;
    node = node.left;
    temp.left = node.right;
    node.right = temp;
    return node;
  }
 
  protected BSTreeNode leftRotation(BSTreeNode node) {
    BSTreeNode temp = node;
    node = node.right;
    temp.right = node.left;
    node.left = temp;
    return node;
  }
 
  public void delete(Object x) {
    rootNode = delete((Comparable)x, rootNode) ;
  }
 
  private Comparable minNodeKey ;
 
  public BSTreeNode delete(Comparable x, BSTreeNode node) {
    if (node != null) {
      if (x.compareTo(node.key) == 0) { // delete node
        if (node.left == null) // empty left
          node = node.right;
        else if (node.right == null) //empty right
          node = node.left;
        else {
          node.right = deleteMin(node.right); // delete min from right
          node.key = minNodeKey; // put it into the node
        }
      }
      else if (x.compareTo(node.key) < 0)
        node.left = delete(x, node.left);
      else
        node.right = delete(x, node.right);
    }
    return node;
  }
 
  private BSTreeNode deleteMin(BSTreeNode node) {
    if (node.left != null){
      node.left = deleteMin(node.left);
      return node ;
    }
    else {
      minNodeKey = node.key;
      return node.right;
    }
  }
 
  public BSTreeNode root() {
    return rootNode;
  }
 
  public void inorder() {
    inorder(root());
  }
 
  private void inorder(BSTreeNode node) {
    if (node != null) {
      inorder(node.left) ;
      System.out.print(node.key+", ");
      inorder(node.right) ;
    }
  }
 
  public void preorder() {
    preorder(root());
  }
 
  private void preorder(BSTreeNode node) {
    if (node != null) {
      System.out.print(node.key+", ");
      preorder(node.left) ;
      preorder(node.right) ;
    }
  }
 
  public void postorder() {
    postorder(root()) ;
  }
 
  private void postorder(BSTreeNode node) {
    if (node != null) {
      postorder(node.left) ;
      postorder(node.right) ;
      System.out.print(node.key+", ");
    }
  }
 
  private boolean printLevel(int l, BSTreeNode r) {
     if (r==null)
       return false ;
     else if (l==1) {
       System.out.print(r.key + ", ") ;
       return true ;
     }
     else
       return printLevel(l-1, r.left) | printLevel(l-1, r.right) ;
  }
 
  public void printByLevel() {
    int l = 1 ;
    while (printLevel(l,root())) {
      l++ ;
      System.out.println() ;
    }
  }
 
  int height(BSTreeNode node) {
     if (node==null) return 0 ;
     else return 1+Math.max(height(node.left), height(node.right)) ;
  }
  public void printTree() {
    int maxDepth=height(rootNode) ;
    final int indent = 3 ;
    StringBuffer iLine = new StringBuffer(indent*maxDepth+1);
    printTree(rootNode, iLine, 0) ;
  }
 
  public void printTree(BSTreeNode node, StringBuffer iLine, int tab) {
     if (node != null) {
       if (node == rootNode) {
         System.out.println(node) ;
       }
       if (node.left != null) {
         System.out.print(iLine+":..") ;
         System.out.println(node.left) ;
         iLine.append(":  ");
         printTree(node.left, iLine,tab+3) ;
       }
       else if (node.right != null) {
         System.out.println(iLine+":..x") ;
         iLine.append(":  ");
       }
       iLine.setLength(tab);
       if (node.right != null) {
         System.out.print(iLine+":..") ;
         System.out.println(node.right) ;
         iLine.append("   ");
         printTree(node.right, iLine, tab + 3);
       }
       else if (node.left != null) {
        System.out.println(iLine+":..x") ;
      }
    }
 }
  public static void main(String[] args) {
    BSTree tree = new BSTree();
    int elements[] = {7,2,5,7,8,3,9} ;
    System.out.print("Inserting:");
    for (int i=0 ; i < elements.length ; i++) {
      tree.insert(new Integer(elements[i]));
      System.out.print(elements[i]+", ") ;
    }
    System.out.print("\nInorder: ");
    tree.inorder() ;
    System.out.println("\nBy level");
    tree.printByLevel();
    System.out.print("\nTree structure: \n");
    tree.printTree() ;
    System.out.print("Deleting:");
    for (int i=0 ; i < elements.length/2+1 ; i++) {
      tree.delete(new Integer(elements[i]));
      System.out.print(elements[i]+", ") ;
    }
    System.out.print("\nInorder: ");
    tree.inorder() ;
  }
 
}