| New file |
|---|
| 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 |
| }; |
| |
| } |