diff options
Diffstat (limited to 'includes/js/dojox/collections/BinaryTree.js')
| -rw-r--r-- | includes/js/dojox/collections/BinaryTree.js | 211 |
1 files changed, 211 insertions, 0 deletions
diff --git a/includes/js/dojox/collections/BinaryTree.js b/includes/js/dojox/collections/BinaryTree.js new file mode 100644 index 0000000..edd9fbf --- /dev/null +++ b/includes/js/dojox/collections/BinaryTree.js @@ -0,0 +1,211 @@ +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 +}; + +} |