1 if(!dojo._hasResource["dojox.collections.BinaryTree"]){ //_hasResource checks added by build. Do not use _hasResource directly in your code.
2 dojo._hasResource["dojox.collections.BinaryTree"] = true;
3 dojo.provide("dojox.collections.BinaryTree");
4 dojo.require("dojox.collections._base");
6 dojox.collections.BinaryTree=function(data){
7 function node(data, rnode, lnode){
9 this.right=rnode||null;
10 this.left=lnode||null;
11 this.clone=function(){
14 c.value=this.value.clone();
19 c.left=this.left.clone();
22 c.right=this.right.clone();
26 this.compare=function(n){
27 if(this.value>n.value){ return 1; }
28 if(this.value<n.value){ return -1; }
31 this.compareData=function(d){
32 if(this.value>d){ return 1; }
33 if(this.value<d){ return -1; }
38 function inorderTraversalBuildup(current, a){
40 inorderTraversalBuildup(current.left, a);
41 a.push(current.value);
42 inorderTraversalBuildup(current.right, a);
46 function preorderTraversal(current, sep){
49 s=current.value.toString() + sep;
50 s+=preorderTraversal(current.left, sep);
51 s+=preorderTraversal(current.right, sep);
55 function inorderTraversal(current, sep){
58 s=inorderTraversal(current.left, sep);
59 s+=current.value.toString() + sep;
60 s+=inorderTraversal(current.right, sep);
64 function postorderTraversal(current, sep){
67 s=postorderTraversal(current.left, sep);
68 s+=postorderTraversal(current.right, sep);
69 s+=current.value.toString() + sep;
74 function searchHelper(current, data){
75 if(!current){ return null; }
76 var i=current.compareData(data);
77 if(i==0){ return current; }
78 if(i>0){ return searchHelper(current.left, data); }
79 else{ return searchHelper(current.right, data); }
82 this.add=function(data){
91 if(i>0){ current=current.left; }
92 else{ current=current.right; }
106 this.clear=function(){
110 this.clone=function(){
111 var c=new dojox.collections.BinaryTree();
112 var itr=this.getIterator();
118 this.contains=function(data){
119 return this.search(data) != null;
121 this.deleteData=function(data){
124 var i=current.compareData(data);
125 while(i!=0&¤t!=null){
128 current=current.left;
131 current=current.right;
133 i=current.compareData(data);
135 if(!current){ return; }
141 i=parent.compare(current);
142 if(i>0){ parent.left=current.left; }
143 else if(i<0){ parent.right=current.left; }
146 else if(!current.right.left){
150 i=parent.compare(current);
151 if(i>0){ parent.left=current.right; }
152 else if(i<0){ parent.right=current.right; }
156 var leftmost=current.right.left;
157 var lmParent=current.right;
158 while(leftmost.left!=null){
160 leftmost=leftmost.left;
162 lmParent.left=leftmost.right;
163 leftmost.left=current.left;
164 leftmost.right=current.right;
168 i=parent.compare(current);
169 if(i>0){ parent.left=leftmost; }
170 else if(i<0){ parent.right=leftmost; }
174 this.getIterator=function(){
176 inorderTraversalBuildup(root, a);
177 return new dojox.collections.Iterator(a);
179 this.search=function(data){
180 return searchHelper(root, data);
182 this.toString=function(order, sep){
183 if(!order){ order=dojox.collections.BinaryTree.TraversalMethods.Inorder; }
187 case dojox.collections.BinaryTree.TraversalMethods.Preorder:
188 s=preorderTraversal(root, sep);
190 case dojox.collections.BinaryTree.TraversalMethods.Inorder:
191 s=inorderTraversal(root, sep);
193 case dojox.collections.BinaryTree.TraversalMethods.Postorder:
194 s=postorderTraversal(root, sep);
197 if(s.length==0){ return ""; }
198 else{ return s.substring(0, s.length - sep.length); }
202 var root=this.root=null;
207 dojox.collections.BinaryTree.TraversalMethods={
208 Preorder: 1, Inorder: 2, Postorder: 3