root / trunk / web / dojo / dojox / collections / BinaryTree.js @ 13
History | View | Annotate | Download (3.63 KB)
| 1 | 9 | andrej.cim | /*
|
|---|---|---|---|
| 2 | Copyright (c) 2004-2010, The Dojo Foundation All Rights Reserved.
|
||
| 3 | Available via Academic Free License >= 2.1 OR the modified BSD license.
|
||
| 4 | see: http://dojotoolkit.org/license for details
|
||
| 5 | */
|
||
| 6 | |||
| 7 | |||
| 8 | if(!dojo._hasResource["dojox.collections.BinaryTree"]){ |
||
| 9 | dojo._hasResource["dojox.collections.BinaryTree"]=true; |
||
| 10 | dojo.provide("dojox.collections.BinaryTree");
|
||
| 11 | dojo.require("dojox.collections._base");
|
||
| 12 | dojox.collections.BinaryTree=function(_1){ |
||
| 13 | function _2(_3,_4,_5){ |
||
| 14 | this.value=_3||null; |
||
| 15 | this.right=_4||null; |
||
| 16 | this.left=_5||null; |
||
| 17 | this.clone=function(){ |
||
| 18 | var c=new _2(); |
||
| 19 | if(this.value.value){ |
||
| 20 | c.value=this.value.clone();
|
||
| 21 | }else{
|
||
| 22 | c.value=this.value;
|
||
| 23 | } |
||
| 24 | if(this.left!=null){ |
||
| 25 | c.left=this.left.clone();
|
||
| 26 | } |
||
| 27 | if(this.right!=null){ |
||
| 28 | c.right=this.right.clone();
|
||
| 29 | } |
||
| 30 | return c;
|
||
| 31 | }; |
||
| 32 | this.compare=function(n){ |
||
| 33 | if(this.value>n.value){ |
||
| 34 | return 1; |
||
| 35 | } |
||
| 36 | if(this.value<n.value){ |
||
| 37 | return -1; |
||
| 38 | } |
||
| 39 | return 0; |
||
| 40 | }; |
||
| 41 | this.compareData=function(d){ |
||
| 42 | if(this.value>d){ |
||
| 43 | return 1; |
||
| 44 | } |
||
| 45 | if(this.value<d){ |
||
| 46 | return -1; |
||
| 47 | } |
||
| 48 | return 0; |
||
| 49 | }; |
||
| 50 | }; |
||
| 51 | function _6(_7,a){ |
||
| 52 | if(_7){
|
||
| 53 | _6(_7.left,a); |
||
| 54 | a.push(_7.value); |
||
| 55 | _6(_7.right,a); |
||
| 56 | } |
||
| 57 | }; |
||
| 58 | function _8(_9,_a){ |
||
| 59 | var s=""; |
||
| 60 | if(_9){
|
||
| 61 | s=_9.value.toString()+_a; |
||
| 62 | s+=_8(_9.left,_a); |
||
| 63 | s+=_8(_9.right,_a); |
||
| 64 | } |
||
| 65 | return s;
|
||
| 66 | }; |
||
| 67 | function _b(_c,_d){ |
||
| 68 | var s=""; |
||
| 69 | if(_c){
|
||
| 70 | s=_b(_c.left,_d); |
||
| 71 | s+=_c.value.toString()+_d; |
||
| 72 | s+=_b(_c.right,_d); |
||
| 73 | } |
||
| 74 | return s;
|
||
| 75 | }; |
||
| 76 | function _e(_f,sep){ |
||
| 77 | var s=""; |
||
| 78 | if(_f){
|
||
| 79 | s=_e(_f.left,sep); |
||
| 80 | s+=_e(_f.right,sep); |
||
| 81 | s+=_f.value.toString()+sep; |
||
| 82 | } |
||
| 83 | return s;
|
||
| 84 | }; |
||
| 85 | function _10(_11,_12){ |
||
| 86 | if(!_11){
|
||
| 87 | return null; |
||
| 88 | } |
||
| 89 | var i=_11.compareData(_12);
|
||
| 90 | if(i==0){ |
||
| 91 | return _11;
|
||
| 92 | } |
||
| 93 | if(i>0){ |
||
| 94 | return _10(_11.left,_12);
|
||
| 95 | }else{
|
||
| 96 | return _10(_11.right,_12);
|
||
| 97 | } |
||
| 98 | }; |
||
| 99 | this.add=function(_13){ |
||
| 100 | var n=new _2(_13); |
||
| 101 | var i;
|
||
| 102 | var _14=_15;
|
||
| 103 | var _16=null; |
||
| 104 | while(_14){
|
||
| 105 | i=_14.compare(n); |
||
| 106 | if(i==0){ |
||
| 107 | return;
|
||
| 108 | } |
||
| 109 | _16=_14; |
||
| 110 | if(i>0){ |
||
| 111 | _14=_14.left; |
||
| 112 | }else{
|
||
| 113 | _14=_14.right; |
||
| 114 | } |
||
| 115 | } |
||
| 116 | this.count++;
|
||
| 117 | if(!_16){
|
||
| 118 | _15=n; |
||
| 119 | }else{
|
||
| 120 | i=_16.compare(n); |
||
| 121 | if(i>0){ |
||
| 122 | _16.left=n; |
||
| 123 | }else{
|
||
| 124 | _16.right=n; |
||
| 125 | } |
||
| 126 | } |
||
| 127 | }; |
||
| 128 | this.clear=function(){ |
||
| 129 | _15=null;
|
||
| 130 | this.count=0; |
||
| 131 | }; |
||
| 132 | this.clone=function(){ |
||
| 133 | var c=new dojox.collections.BinaryTree(); |
||
| 134 | var itr=this.getIterator(); |
||
| 135 | while(!itr.atEnd()){
|
||
| 136 | c.add(itr.get()); |
||
| 137 | } |
||
| 138 | return c;
|
||
| 139 | }; |
||
| 140 | this.contains=function(_17){ |
||
| 141 | return this.search(_17)!=null; |
||
| 142 | }; |
||
| 143 | this.deleteData=function(_18){ |
||
| 144 | var _19=_15;
|
||
| 145 | var _1a=null; |
||
| 146 | var i=_19.compareData(_18);
|
||
| 147 | while(i!=0&&_19!=null){ |
||
| 148 | if(i>0){ |
||
| 149 | _1a=_19; |
||
| 150 | _19=_19.left; |
||
| 151 | }else{
|
||
| 152 | if(i<0){ |
||
| 153 | _1a=_19; |
||
| 154 | _19=_19.right; |
||
| 155 | } |
||
| 156 | } |
||
| 157 | i=_19.compareData(_18); |
||
| 158 | } |
||
| 159 | if(!_19){
|
||
| 160 | return;
|
||
| 161 | } |
||
| 162 | this.count--;
|
||
| 163 | if(!_19.right){
|
||
| 164 | if(!_1a){
|
||
| 165 | _15=_19.left; |
||
| 166 | }else{
|
||
| 167 | i=_1a.compare(_19); |
||
| 168 | if(i>0){ |
||
| 169 | _1a.left=_19.left; |
||
| 170 | }else{
|
||
| 171 | if(i<0){ |
||
| 172 | _1a.right=_19.left; |
||
| 173 | } |
||
| 174 | } |
||
| 175 | } |
||
| 176 | }else{
|
||
| 177 | if(!_19.right.left){
|
||
| 178 | if(!_1a){
|
||
| 179 | _15=_19.right; |
||
| 180 | }else{
|
||
| 181 | i=_1a.compare(_19); |
||
| 182 | if(i>0){ |
||
| 183 | _1a.left=_19.right; |
||
| 184 | }else{
|
||
| 185 | if(i<0){ |
||
| 186 | _1a.right=_19.right; |
||
| 187 | } |
||
| 188 | } |
||
| 189 | } |
||
| 190 | }else{
|
||
| 191 | var _1b=_19.right.left;
|
||
| 192 | var _1c=_19.right;
|
||
| 193 | while(_1b.left!=null){ |
||
| 194 | _1c=_1b; |
||
| 195 | _1b=_1b.left; |
||
| 196 | } |
||
| 197 | _1c.left=_1b.right; |
||
| 198 | _1b.left=_19.left; |
||
| 199 | _1b.right=_19.right; |
||
| 200 | if(!_1a){
|
||
| 201 | _15=_1b; |
||
| 202 | }else{
|
||
| 203 | i=_1a.compare(_19); |
||
| 204 | if(i>0){ |
||
| 205 | _1a.left=_1b; |
||
| 206 | }else{
|
||
| 207 | if(i<0){ |
||
| 208 | _1a.right=_1b; |
||
| 209 | } |
||
| 210 | } |
||
| 211 | } |
||
| 212 | } |
||
| 213 | } |
||
| 214 | }; |
||
| 215 | this.getIterator=function(){ |
||
| 216 | var a=[];
|
||
| 217 | _6(_15,a); |
||
| 218 | return new dojox.collections.Iterator(a); |
||
| 219 | }; |
||
| 220 | this.search=function(_1d){ |
||
| 221 | return _10(_15,_1d);
|
||
| 222 | }; |
||
| 223 | this.toString=function(_1e,sep){ |
||
| 224 | if(!_1e){
|
||
| 225 | _1e=dojox.collections.BinaryTree.TraversalMethods.Inorder; |
||
| 226 | } |
||
| 227 | if(!sep){
|
||
| 228 | sep=",";
|
||
| 229 | } |
||
| 230 | var s=""; |
||
| 231 | switch(_1e){
|
||
| 232 | case dojox.collections.BinaryTree.TraversalMethods.Preorder:
|
||
| 233 | s=_8(_15,sep); |
||
| 234 | break;
|
||
| 235 | case dojox.collections.BinaryTree.TraversalMethods.Inorder:
|
||
| 236 | s=_b(_15,sep); |
||
| 237 | break;
|
||
| 238 | case dojox.collections.BinaryTree.TraversalMethods.Postorder:
|
||
| 239 | s=_e(_15,sep); |
||
| 240 | break;
|
||
| 241 | } |
||
| 242 | if(s.length==0){ |
||
| 243 | return ""; |
||
| 244 | }else{
|
||
| 245 | return s.substring(0,s.length-sep.length); |
||
| 246 | } |
||
| 247 | }; |
||
| 248 | this.count=0; |
||
| 249 | var _15=this.root=null; |
||
| 250 | if(_1){
|
||
| 251 | this.add(_1);
|
||
| 252 | } |
||
| 253 | }; |
||
| 254 | dojox.collections.BinaryTree.TraversalMethods={Preorder:1,Inorder:2,Postorder:3};
|
||
| 255 | } |