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":""); } }
削除と追加を適当に実装したので、また後で改良してみる。