Site Search:

Binary Search Tree -- UI code

<script src="https://code.jquery.com/jquery-1.4.1.min.js"></script>
<script language="javascript" type="text/javascript">
var BinarySearchTree = function(value) {
  var instance = Object.create(BinarySearchTree.prototype);
    instance.value = value;
    instance.N = 1;
    instance.right = undefined;
    instance.left = undefined;
  return instance
};

BinarySearchTree.prototype.insert = function (value) {
  var node = BinarySearchTree(value);

  function recurse(bst) {
    if (bst.value > value && bst.left === undefined) {
      bst.left = node;    
    } else if (bst.value > value) {
      recurse(bst.left);
    } else if (bst.value < value && bst.right === undefined) {
      bst.right = node;
    } else if (bst.value < value) {
      recurse(bst.right);
    }
    bst.N = bst.N + 1;
  }
 
  recurse(this);
}

BinarySearchTree.prototype.contains = function (value) {
  var doesContain = false;

  function recurse(bst) {
    if (bst.value === value) {
      doesContain = true;;
    } else if (bst.left !== undefined && value < bst.value) {
      recurse(bst.left);
    } else if (bst.right !== undefined && value > bst.value) {
      recurse(bst.right)
    }
  }

  recurse(this);
  return doesContain;
}

BinarySearchTree.prototype.min = function() {
  function min(bst) {
    if(bst.left === undefined) return bst;
    return min(bst.left);
  }
 
  return min(this);
}

BinarySearchTree.prototype.deleteMin = function() {
  function deleteMin(bst) {
    if(bst.left === undefined) return bst.right;
    bst.left = deleteMin(bst.left);
    bst.N = bst.N - 1;
    return bst;
  }
  return deleteMin(this);
}


BinarySearchTree.prototype.delete = function(value) {
  var decrease = 0;
  function deleteN(bst) {  
    if(bst === undefined) return undefined;
    if(value < bst.value) {
      bst.left = deleteN(bst.left);
    }
    else if(value > bst.value) {
      bst.right = deleteN(bst.right);
    } else {
      decrease = 1;
      if(bst.right == undefined) return bst.left;
      if(bst.left == undefined) return bst.right;
      var t = bst;
      bst = t.right.min();
      bst.right = t.right.deleteMin();
      bst.left = t.left;
    }

    if(bst !== undefined) {
      bst.N = bst.N - decrease;
    } else {
      alert('should not be here')
    }  
    return bst;
  }

  return deleteN(this);
}

BinarySearchTree.prototype.size = function() {
  function size(bst) {
    if(bst === undefined) return 0;
    else return bst.N;
  }
 
  return size(this);
}

BinarySearchTree.prototype.depthFirstLog = function (callback) {

  function recurse(bst) {
    if(bst === undefined) return;
    callback.call(bst, bst.value)

    if (bst.left !== undefined) {
      recurse(bst.left)
    }

    if (bst.right !== undefined) {
      recurse(bst.right);
    }
  }

  recurse(this);
}

BinarySearchTree.prototype.genHtml = function() {
  var content = '<ul>\n';

  function genHtml_F(bst, pos) {

    function printNode() { 
        content += '<div class="';
        content += pos;
        content += '">
';
        content += bst.value;
        content += '</div>
\n';         
    }
    if(bst.left === undefined && bst.right === undefined) {
        content += '
<li>\n'
        printNode(); 
        content += '</li>
\n';
        return;
    } 

    content += '
<li>\n'
    printNode();
    if(bst.left !== undefined) {        
        content += '<ul>\n'
        genHtml_F(bst.left, 'left');
        content += '</ul>
\n'
    } 
    
    if(bst.right !== undefined) {
        content += '<ul>\n'
        genHtml_F(bst.right, 'right');
        content += '</ul>
\n'
    }
    content += '</li>
\n';
  }

  genHtml_F(this, 'root');

  content += '</ul>
\n';
  return content;

}


function UI() {

try {
  var tree = new BinarySearchTree(5);
  tree.insert(3);
  tree.insert(9);
  tree.insert(2);
  tree.insert(7);
  tree.insert(1);
  tree.insert(13);

  var a = [];

  var Callback = function() {
    var instance = Object.create(Callback.prototype);
    return instance
  };

  Callback.prototype.call = function (value1, value2) {
    a.push(value2);
  }
  var callback = new Callback();
  tree.depthFirstLog(callback);
  alert('bst start value: ' + a + ' size: ' + tree.size() + ' min: ' + tree.min().value + ' contains(3): ' + tree.contains(3) + ' contains(19): ' + tree.contains(19) );

  alert(tree.genHtml());
  $('#showCase').html(tree.genHtml());
} catch(err) {
  alert(err);
}

}
</script>


<button onclick="UI()">build tree</button>

<br />
<div id="showCase">
</div>