dojo.provide("dojo.collections.BinaryTree");
dojo.require("dojo.collections.Collections");
dojo.require("dojo.experimental");
dojo.experimental("dojo.collections.BinaryTree");
dojo.collections.BinaryTree=function(data){
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) c.left=this.left.clone();
if (this.right) c.right=this.right.clone();
}
this.compare=function(n){
if (this.value > n.value) return 1;
if (this.value < n.value) return -1;
return 0;
}
this.compareData=function(d){
if (this.value > d) return 1;
if (this.value < d) return -1;
return 0;
}
}
function inorderTraversalBuildup(current, a){
if (current){
inorderTraversalBuildup(current.left, a);
a.add(current);
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 dojo.collections.BinaryTree();
c.root=root.clone();
c.count=this.count;
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 && current != 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 dojo.collections.Iterator(a);
};
this.search=function(data){
return searchHelper(root, data);
};
this.toString=function(order, sep){
if (!order) var order=dojo.collections.BinaryTree.TraversalMethods.Inorder;
if (!sep) var sep=" ";
var s="";
switch (order){
case dojo.collections.BinaryTree.TraversalMethods.Preorder:
s=preorderTraversal(root, sep);
break;
case dojo.collections.BinaryTree.TraversalMethods.Inorder:
s=inorderTraversal(root, sep);
break;
case dojo.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);
}
}
dojo.collections.BinaryTree.TraversalMethods={
Preorder : 1,
Inorder : 2,
Postorder : 3
};