git.pond.sub.org Git - eow/blob - static/dojo-release-1.1.1/dojox/collections/BinaryTree.js

   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");
   5
   6 dojox.collections.BinaryTree=function(data){
   7         function node(data, rnode, lnode){
   8                 this.value=data||null;
   9                 this.right=rnode||null;
  10                 this.left=lnode||null;
  11                 this.clone=function(){
  12                         var c=new node();
  13                         if(this.value.value){
  14                                 c.value=this.value.clone();
  15                         }else{
  16                                 c.value=this.value;
  17                         }
  18                         if(this.left!=null){
  19                                 c.left=this.left.clone();
  20                         }
  21                         if(this.right!=null){
  22                                 c.right=this.right.clone();
  23                         }
  24                         return c;
  25                 }
  26                 this.compare=function(n){
  27                         if(this.value>n.value){ return 1; }
  28                         if(this.value<n.value){ return -1; }
  29                         return 0;
  30                 }
  31                 this.compareData=function(d){
  32                         if(this.value>d){ return 1; }
  33                         if(this.value<d){ return -1; }
  34                         return 0;
  35                 }
  36         }
  37
  38         function inorderTraversalBuildup(current, a){
  39                 if(current){
  40                         inorderTraversalBuildup(current.left, a);
  41                         a.push(current.value);
  42                         inorderTraversalBuildup(current.right, a);
  43                 }
  44         }
  45
  46         function preorderTraversal(current, sep){
  47                 var s="";
  48                 if (current){
  49                         s=current.value.toString() + sep;
  50                         s+=preorderTraversal(current.left, sep);
  51                         s+=preorderTraversal(current.right, sep);
  52                 }
  53                 return s;
  54         }
  55         function inorderTraversal(current, sep){
  56                 var s="";
  57                 if (current){
  58                         s=inorderTraversal(current.left, sep);
  59                         s+=current.value.toString() + sep;
  60                         s+=inorderTraversal(current.right, sep);
  61                 }
  62                 return s;
  63         }
  64         function postorderTraversal(current, sep){
  65                 var s="";
  66                 if (current){
  67                         s=postorderTraversal(current.left, sep);
  68                         s+=postorderTraversal(current.right, sep);
  69                         s+=current.value.toString() + sep;
  70                 }
  71                 return s;
  72         }
  73
  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); }
  80         }
  81
  82         this.add=function(data){
  83                 var n=new node(data);
  84                 var i;
  85                 var current=root;
  86                 var parent=null;
  87                 while(current){
  88                         i=current.compare(n);
  89                         if(i==0){ return; }
  90                         parent=current;
  91                         if(i>0){ current=current.left; }
  92                         else{ current=current.right; }
  93                 }
  94                 this.count++;
  95                 if(!parent){
  96                         root=n;
  97                 }else{
  98                         i=parent.compare(n);
  99                         if(i>0){
 100                                 parent.left=n;
 101                         }else{
 102                                 parent.right=n;
 103                         }
 104                 }
 105         };
 106         this.clear=function(){
 107                 root=null;
 108                 this.count=0;
 109         };
 110         this.clone=function(){
 111                 var c=new dojox.collections.BinaryTree();
 112                 var itr=this.getIterator();
 113                 while(!itr.atEnd()){
 114                         c.add(itr.get());
 115                 }
 116                 return c;
 117         };
 118         this.contains=function(data){
 119                 return this.search(data) != null;
 120         };
 121         this.deleteData=function(data){
 122                 var current=root;
 123                 var parent=null;
 124                 var i=current.compareData(data);
 125                 while(i!=0&&current!=null){
 126                         if(i>0){
 127                                 parent=current;
 128                                 current=current.left;
 129                         }else if(i<0){
 130                                 parent=current;
 131                                 current=current.right;
 132                         }
 133                         i=current.compareData(data);
 134                 }
 135                 if(!current){ return; }
 136                 this.count--;
 137                 if(!current.right){
 138                         if(!parent){
 139                                 root=current.left;
 140                         }else{
 141                                 i=parent.compare(current);
 142                                 if(i>0){ parent.left=current.left; }
 143                                 else if(i<0){ parent.right=current.left; }
 144                         }
 145                 }
 146                 else if(!current.right.left){
 147                         if(!parent){
 148                                 root=current.right;
 149                         }else{
 150                                 i=parent.compare(current);
 151                                 if(i>0){ parent.left=current.right; }
 152                                 else if(i<0){ parent.right=current.right; }
 153                         }
 154                 }
 155                 else{
 156                         var leftmost=current.right.left;
 157                         var lmParent=current.right;
 158                         while(leftmost.left!=null){
 159                                 lmParent=leftmost;
 160                                 leftmost=leftmost.left;
 161                         }
 162                         lmParent.left=leftmost.right;
 163                         leftmost.left=current.left;
 164                         leftmost.right=current.right;
 165                         if(!parent){
 166                                 root=leftmost;
 167                         }else{
 168                                 i=parent.compare(current);
 169                                 if(i>0){ parent.left=leftmost; }
 170                                 else if(i<0){ parent.right=leftmost; }
 171                         }
 172                 }
 173         };
 174         this.getIterator=function(){
 175                 var a=[];
 176                 inorderTraversalBuildup(root, a);
 177                 return new dojox.collections.Iterator(a);
 178         };
 179         this.search=function(data){
 180                 return searchHelper(root, data);
 181         };
 182         this.toString=function(order, sep){
 183                 if(!order){ order=dojox.collections.BinaryTree.TraversalMethods.Inorder; }
 184                 if(!sep){ sep=","; }
 185                 var s="";
 186                 switch(order){
 187                         case dojox.collections.BinaryTree.TraversalMethods.Preorder:
 188                                 s=preorderTraversal(root, sep);
 189                                 break;
 190                         case dojox.collections.BinaryTree.TraversalMethods.Inorder:
 191                                 s=inorderTraversal(root, sep);
 192                                 break;
 193                         case dojox.collections.BinaryTree.TraversalMethods.Postorder:
 194                                 s=postorderTraversal(root, sep);
 195                                 break;
 196                 };
 197                 if(s.length==0){ return ""; }
 198                 else{ return s.substring(0, s.length - sep.length); }
 199         };
 200
 201         this.count=0;
 202         var root=this.root=null;
 203         if(data){
 204                 this.add(data);
 205         }
 206 }
 207 dojox.collections.BinaryTree.TraversalMethods={
 208         Preorder: 1, Inorder: 2, Postorder: 3
 209 };
 210
 211 }