--- /dev/null
+if(!dojo._hasResource["dojox.collections.BinaryTree"]){ //_hasResource checks added by build. Do not use _hasResource directly in your code.
+dojo._hasResource["dojox.collections.BinaryTree"] = true;
+dojo.provide("dojox.collections.BinaryTree");
+dojo.require("dojox.collections._base");
+
+dojox.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!=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<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.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);
+ }
+}
+dojox.collections.BinaryTree.TraversalMethods={
+ Preorder: 1, Inorder: 2, Postorder: 3
+};
+
+}
projects / eow / blobdiff