2分木を作ってみた

大学のTAで、2年生向けに二分木をCで実装する実験をした。
復習がてら、Javaで二分木を実装したので、載せてみる。

BinaryTree.java

public class BinaryTree<E extends Comparable<E>> {
  BinaryNode root;

  //生成
  public BinaryTree(){
    root=null;
  }

  //挿入
  public void insert(E t){
    if(root==null){
      root=new BinaryNode(t);
      return;
    }

    BinaryNode cur=root;
    BinaryNode parent=null;
    boolean isLeft=false;

    while(cur!=null){
      if(cur.e.compareTo(t)>0){
        isLeft=true;
        parent=cur;
        cur=cur.left;
      }else if(cur.e.compareTo(t)<0){
        isLeft=false;
        parent=cur;
        cur=cur.right;
      }else if(cur.e.compareTo(t)==0){
        System.out.println("This element has already exit!");
        return;
      }else{
        System.out.println("Error! exit this program");
        System.exit(1);
      }
    }
    cur=new BinaryNode(parent,t);
    if(isLeft)
      parent.left=cur;
    else
      parent.right=cur;
  }

  //検索
  public BinaryNode search(E t){
    BinaryNode cur=root;

    while(cur!=null){
      if(cur.e.compareTo(t)==0)
        break;

      else if(cur.e.compareTo(t)>0)
        cur=cur.left;
      else if(cur.e.compareTo(t)<0)
        cur=cur.right;

      else{
        System.out.println("This Element don't exit");
        cur=null;
      }
    }
    return cur;
  }

  //要素を削除
  public void remove(E t){
    BinaryNode cur=search(t);
    BinaryNode parent=cur.parent;
    if(cur!=null){
      //子を持たない時
      if(cur.left==null && cur.right==null){
        if(cur.e.compareTo(parent.e)>0)
          parent.left=null;
        else
          parent.right=null;
      }

      //子を1つしか持たない時
      else if(cur.left==null){
        if(cur.e.compareTo(parent.e)>0){
          parent.left=cur.right;
        }else{
          parent.right=cur.right;
        }
        cur.right.parent=parent;
      }else if(cur.right==null){
        if(cur.e.compareTo(parent.e)>0){
          parent.left=cur.left;
        }else{
          parent.right=cur.left;
        }
        cur.left.parent=parent;
      }

      //子を2つもつ時
      else{
        int l=getDepth(cur.left);
        int r=getDepth(cur.right);
        if(l>r){
          BinaryNode max=removeMax(cur.left);
          if(parent.e.compareTo(max.e)>0)
            parent.left=max;
          else
            parent.right=max;
        }else{
          BinaryNode min=removeMin(cur.right);
          if(parent.e.compareTo(min.e)>0)
            parent.left=min;
          else
            parent.right=min;
        }
      }
    }
  }

  //最大の要素を削除する
  public BinaryNode removeMax(BinaryNode cur){
    BinaryNode parent=cur.parent;
    while(cur!=null){
      parent=cur;
      cur=cur.right;
    }
    parent.parent.right=null;
    return parent;
  }

  //最小の要素を削除する
  public BinaryNode removeMin(BinaryNode cur){
    BinaryNode parent=cur.parent;
    while(cur!=null){
      parent=cur;
      cur=cur.left;
    }
    parent.parent.left=null;
    return parent;
  }

  //ノードから深さを取得する
  public int getDepth(BinaryNode cur){
    if(cur==null)
      return -1;

    int l,r;
    l=r=0;
    l=getDepth(cur.left)+1;
    r=getDepth(cur.right)+1;

    return (l>r)?l:r;
  }
  
  //木の要素を表示する
  public String toString(){
    return ""+root;
  }
}

BinaryNode.java

public class BinaryNode<E extends Comparable<E>> {

  BinaryNode parent;
  BinaryNode left,right;
  E e;

  public BinaryNode(E t){
    parent=null;
    left=right=null;
    e=t;
  }

  public BinaryNode(BinaryNode parent,E t){
    this.parent=parent;
    e=t;
  }
  
  public String toString(){
    String sl=(left!=null)?"  "+left+"\n":"";
    String sr=(right!=null)?"  "+right+"\n":"";
    return "  "+e+"\n"+sl+""+sr;
      //return ""+e+"\n"+((left!=null)?"  "+left+"\n":"")+""+((right!=null)?"  "+right+"\n":"");
  }
}

削除と追加を適当に実装したので、また後で改良してみる。