<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>