در قسمت زیر کد یکی از مهمترین قسمت های ساختمان داده نوشته شده به زبان جاوا (چندان فرقی با سی++ ندارد به جز کلاس BinaryNode که باید لینک های چپ و راست در سی++ از نوع اشاره گر باشند)
این کلاس شامل متدهایی برای حذف /اضافه و جستجو و می توان با اضافه کردن متدی که درخت را به صورت میان ترتیب(inorder) طی می کند یک جستجو و مرتب سازی بسیار سریع را داست چراکه در حالت متوسط و در بدترین حالت تنها دارای هزینه ی nlogn است و تنها بدی آن مقدار حافظه ی مصرفی یعنی n،تعداد گره ها، می باشد .
class BinaryNode<T> {
BinaryNode right;
BinaryNode left;
T value;
BinaryNode parent;
BinaryNode(T value,BinaryNode left,BinaryNode right,BinaryNode parent){
this.right=right;
this.left=left;
this.value=value;
this.parent=parent;
}
BinaryNode(){
this(null,null,null,null);
}
}
public class BSTree {
private BinaryNode root;
public BSTree(){
root=null;
}
public void insert(Comparable x){
root=insert(x,root,root);
}
private Object find(Comparable x, BinaryNode root) {
if(root==null)
return null;
Object p = null;
if(x.compareTo(root.value)>0)
p=find(x,root.right);
else if(x.compareTo(root.value)<0)
p=find(x,root.left);
else if(x.compareTo(root.value)==0)
p=root.value;
else
System.out.print(“Item not founs!”);
return p;
}
private BinaryNode insert(Comparable x, BinaryNode root,BinaryNode p) {
if(root==null)
root=new BinaryNode(x,null,null,p);
else if(x.compareTo(root.value)>0)
root.right=insert(x,root.right,root);
else if(x.compareTo(root.value)<0)
root.left=insert(x,root.left,root);
return root;
}
private void remove(Comparable x){
root=remove(x,root);
}
private BinaryNode remove(Comparable x, BinaryNode root) {
if(root==null)
return root;
else if(x.compareTo(root.value)>0)
root.right=remove(x,root.right);
else if(x.compareTo(root.value)<0)
root.left=remove(x,root.left);
else if(x.compareTo(root.value)==0){
if(root.left==null)
root=root.right;
if(root.right==null)
root=root.left;
else{
root.value=rightmost(root.left);
root.left=removmost(root.left);
}
}
return root;
}
private BinaryNode removmost(BinaryNode root) {
if(root.right==null)
return root.left;
else
root=removmost(root.right);
return root;
}
private Object rightmost(BinaryNode root) {
if(root.right==null)
return root.value;
else
return rightmost(root.right);
}
public Object find(Comparable x){
return find(x,root);
}public void print(){
print(root, 1);
}
private void print(BinaryNode root, int depth){
for(int i=1; i<depth; i++)
System.out.print(“ “);
if(root == null){
System.out.println(“null”);
return;
}
if(root.parent!=null)
System.out.println(root.value+ ” , parent”+root.parent.value);
else
System.out.println(root.value);
print(root.left, depth+1);
print(root.right, depth+1);
}
//System.out.println(“1111″);
public static void main(String []args){
BSTree t=new BSTree();
for(int i=0;i<10;i++)
t.insert(Math.round(Math.random()*1000));
t.print();
}
}
