Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Aug 5th, 2012  |  syntax: None  |  size: 3.31 KB  |  hits: 15  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /******************************
  2.  *      class: Binary tree search
  3.  *
  4.  *
  5.  *
  6.  *******************************/
  7.  
  8. var tbst = function (isLower, isGreater, equals) {
  9.        
  10.         this.hi = null;
  11.         this.elem = null;
  12.         this.hd=null;
  13.        
  14.         // Comparators
  15.         this.isLower = isLower;
  16.         this.isGreater = isGreater;
  17.         this.equals = equals;
  18.        
  19.         /**
  20.          *      Retrieves the eldest son
  21.          *      a left subtree
  22.          *      Returns an element
  23.          */
  24.          this.mayor = function (tbst) {
  25.                  
  26.                  if (! tbst.hd.isEmpty()) {
  27.                          
  28.                          return tbst.mayor(this.hd);
  29.                          
  30.                  }else {
  31.                          
  32.                          return tbst.elem;
  33.                          
  34.                  }
  35.          }
  36. }
  37.  
  38. tbst.prototype.isLeaf = function () {
  39.        
  40.         return (this.hi==null) && (this.hd==null);
  41. }
  42.  
  43.  
  44. tbst.prototype.isEmpty = function () {
  45.        
  46.         return (this.elem==null);
  47. }
  48.  
  49. tbst.prototype.clone = function () {
  50.         if (! this.isEmpty()) {
  51.                
  52.                 var bst = new tbst(this.isLower,this.isGreater,this.equals);
  53.                 bst.elem = this.elem;
  54.                 bst.hi = this.hi.clone();
  55.                 bst.hd = this.hd.clone();
  56.                 return bst;
  57.                
  58.         }else {
  59.                 return null;
  60.         }
  61.        
  62. }
  63. // deleting an element
  64. tbst.prototype.eliminar = function (e){
  65.        
  66.         if (! this.isEmpty() ) {
  67.                
  68.                 if ( this.isLower(e , this.elem) ) {
  69.                        
  70.                         this.hi.eliminar(e);
  71.                        
  72.                 }else if ( this.isGreater(e , this.elem )) {
  73.                        
  74.                         this.hd.eliminar(e);
  75.                        
  76.                  }else { // Hay que eliminarlo
  77.                               // hi = null
  78.                           if ( this.hd && this.hi.isEmpty()) {
  79.                                  
  80.                                   this.elem= this.hd.elem;
  81.                                   delete this.hd;
  82.                                   this.hd= new tbst(this.isLower,this.isGreater,this.equals);
  83.                                  
  84.                           }else if ( this.hi && this.hd.isEmpty() ) {
  85.                                   // hd = null
  86.                                   this.elem = this.hi.elem;
  87.                                   delete this.hi;
  88.                                   this.hi = new tbst(this.isLower,this.isGreater,this.equals);
  89.                                  
  90.                           }else {
  91.                                   // hi!= null && hd!= null
  92.                                   var tbstMayor = this.mayor(this.hi);
  93.                                   this.elem = tbstMayor;
  94.                                   this.hi.eliminar(tbstMayor);
  95.                                  
  96.                           }
  97.                  }
  98.                  
  99.         }
  100.        
  101. }
  102.  
  103. // inserting an element
  104. tbst.prototype.insertar = function (e){
  105.        
  106.         if ( this.isEmpty() ) {
  107.                
  108.                 this.elem = e;
  109.                 this.hi = new tbst(this.isLower,this.isGreater,this.equals);
  110.                 this.hd = new tbst(this.isLower,this.isGreater,this.equals);
  111.                
  112.         }else {
  113.                
  114.                 if (this.isLower (e , this.elem) ) {
  115.                        
  116.                         this.hi.insertar(e);
  117.                        
  118.                 }else if (this.isGreater (e , this.elem )){
  119.                        
  120.                         this.hd.insertar(e);
  121.                        
  122.                 }else
  123.                         throw new Error ("equal");
  124.                
  125.         }
  126.        
  127. }
  128.  
  129. // pre-order traversal
  130. tbst.prototype.preorder = function (arr) {
  131.        
  132.         if (! this.isEmpty()) {
  133.                
  134.                 arr.push(this.elem);
  135.                 this.hi.inorder(arr);
  136.                 this.hd.inorder(arr);
  137.                
  138.         }
  139. }
  140.  
  141. // in-order traversal
  142. tbst.prototype.inorder = function (arr) {
  143.        
  144.         if (! this.isEmpty()) {
  145.                
  146.                 this.hi.inorder(arr);
  147.                 arr.push(this.elem);
  148.                 this.hd.inorder(arr);
  149.                
  150.         }
  151. }
  152.  
  153. // post-order traversal
  154. tbst.prototype.postorder = function (arr) {
  155.        
  156.         if (! this.isEmpty()) {
  157.                
  158.                 this.hi.inorder(arr);
  159.                 this.hd.inorder(arr);
  160.                 arr.push(this.elem);
  161.  
  162.         }
  163. }
  164.  
  165. //Travel width
  166. tbst.prototype.bfs = function (lista){
  167.        
  168.         // Cola
  169.         var arr = new Array();
  170.         if (! this.isEmpty ()) {
  171.                
  172.                 arr.push(this);
  173.                 var i= 0;
  174.                 while (arr[i]) {
  175.                        
  176.                         lista.push(arr[i].elem);
  177.                        
  178.                         if (! arr[i].hi.isEmpty()) {
  179.                                 arr.push(arr[i].hi);
  180.                         }
  181.                        
  182.                         if (! arr[i].hd.isEmpty()) {
  183.                                 arr.push(arr[i].hd);
  184.                         }
  185.                        
  186.                         if (i!= arr.length)
  187.                                 delete arr[i];
  188.                                
  189.                         i++;
  190.                        
  191.                 }
  192.         }
  193. }
create a new version of this paste RAW Paste Data