source: [view]
function node(data, rnode, lnode){
this.value=data||null;
this.right=rnode||null;
this.left=lnode||null;
this.clone=function(){
var c=new node();
if(this.value.value){
c.value=this.value.clone();
}else{
c.value=this.value;
}
if(this.left!=null){
c.left=this.left.clone();
}
if(this.right!=null){
c.right=this.right.clone();
}
return c;
}
this.compare=function(n){
if(this.value>n.value){ return 1; }
if(this.value return 0;
}
this.compareData=function(d){
if(this.value>d){ return 1; }
if(this.value return 0;
}
}
function inorderTraversalBuildup(current, a){
if(current){
inorderTraversalBuildup(current.left, a);
a.push(current.value);
inorderTraversalBuildup(current.right, a);
}
}
function preorderTraversal(current, sep){
var s="";
if (current){
s=current.value.toString() + sep;
s+=preorderTraversal(current.left, sep);
s+=preorderTraversal(current.right, sep);
}
return s;
}
function inorderTraversal(current, sep){
var s="";
if (current){
s=inorderTraversal(current.left, sep);
s+=current.value.toString() + sep;
s+=inorderTraversal(current.right, sep);
}
return s;
}
function postorderTraversal(current, sep){
var s="";
if (current){
s=postorderTraversal(current.left, sep);
s+=postorderTraversal(current.right, sep);
s+=current.value.toString() + sep;
}
return s;
}
function searchHelper(current, data){
if(!current){ return null; }
var i=current.compareData(data);
if(i==0){ return current; }
if(i>0){ return searchHelper(current.left, data); }
else{ return searchHelper(current.right, data); }
}
this.add=function(data){
var n=new node(data);
var i;
var current=root;
var parent=null;
while(current){
i=current.compare(n);
if(i==0){ return; }
parent=current;
if(i>0){ current=current.left; }
else{ current=current.right; }
}
this.count++;
if(!parent){
root=n;
}else{
i=parent.compare(n);
if(i>0){
parent.left=n;
}else{
parent.right=n;
}
}
};
this.clear=function(){
root=null;
this.count=0;
};
this.clone=function(){
var c=new dojox.collections.BinaryTree();
var itr=this.getIterator();
while(!itr.atEnd()){
c.add(itr.get());
}
return c;
};
this.contains=function(data){
return this.search(data) != null;
};
this.deleteData=function(data){
var current=root;
var parent=null;
var i=current.compareData(data);
while(i!=0&¤t!=null){
if(i>0){
parent=current;
current=current.left;
}else if(i<0){
parent=current;
current=current.right;
}
i=current.compareData(data);
}
if(!current){ return; }
this.count--;
if(!current.right){
if(!parent){
root=current.left;
}else{
i=parent.compare(current);
if(i>0){ parent.left=current.left; }
else if(i<0){ parent.right=current.left; }
}
}
else if(!current.right.left){
if(!parent){
root=current.right;
}else{
i=parent.compare(current);
if(i>0){ parent.left=current.right; }
else if(i<0){ parent.right=current.right; }
}
}
else{
var leftmost=current.right.left;
var lmParent=current.right;
while(leftmost.left!=null){
lmParent=leftmost;
leftmost=leftmost.left;
}
lmParent.left=leftmost.right;
leftmost.left=current.left;
leftmost.right=current.right;
if(!parent){
root=leftmost;
}else{
i=parent.compare(current);
if(i>0){ parent.left=leftmost; }
else if(i<0){ parent.right=leftmost; }
}
}
};
this.getIterator=function(){
var a=[];
inorderTraversalBuildup(root, a);
return new dojox.collections.Iterator(a);
};
this.search=function(data){
return searchHelper(root, data);
};
this.toString=function(order, sep){
if(!order){ order=dojox.collections.BinaryTree.TraversalMethods.Inorder; }
if(!sep){ sep=","; }
var s="";
switch(order){
case dojox.collections.BinaryTree.TraversalMethods.Preorder:
s=preorderTraversal(root, sep);
break;
case dojox.collections.BinaryTree.TraversalMethods.Inorder:
s=inorderTraversal(root, sep);
break;
case dojox.collections.BinaryTree.TraversalMethods.Postorder:
s=postorderTraversal(root, sep);
break;
};
if(s.length==0){ return ""; }
else{ return s.substring(0, s.length - sep.length); }
};
this.count=0;
var root=this.root=null;
if(data){
this.add(data);
}