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