<style>
.wfm ul {
list-style: none; /* Remove HTML bullets */
padding: 0;
margin: 10;
}
.wfm li {
padding-left: 16px;
}
.root {
color: green;
font-weight: 900;
}
.left {
color: blue;
}
.right {
color: red;
}
.left:before {
content: "---->"; /* Insert content that looks like bullets */
padding-right: 8px;
color: blue;
}
.right:before {
content: "---->"; /* Insert content that looks like bullets */
padding-right: 8px;
color: red;
}
.btn button {
margin: 5px;
}
.delimiter {
width: 100%;
background-color: rgba(0, 255, 0, 0.3);
border: 5px none red;
}
#insertCode deleteCode deleteMinCode {
visibility: none;
}
</style>
<script src="https://code.jquery.com/jquery-1.4.1.min.js"></script>
<script type="text/javascript" language="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;
}
var myTree = undefined;
function addNode() {
try {
$('#previous').html($('#showCase').html());
var nodeVal = document.getElementById('nodeValue').value;
nodeVal = parseInt(nodeVal);
if(myTree === undefined) {
myTree = new BinarySearchTree(nodeVal);
} else {
myTree.insert(nodeVal);
}
$('#showCase').html(myTree.genHtml());
} catch (err) {
alert(err);
}
}
function removeNode() {
try {
$('#previous').html($('#showCase').html());
var nodeVal = document.getElementById('nodeValue').value;
nodeVal = parseInt(nodeVal);
if(myTree !== undefined) {
myTree = myTree.delete(nodeVal);
}
if(myTree !== undefined) {
$('#showCase').html(myTree.genHtml());
} else {
$('#showCase').html('tree deleted');
}
} catch (err) {
alert(err);
}
}
function removeMin() {
try {
$('#previous').html($('#showCase').html());
if(myTree !== undefined) {
myTree = myTree.deleteMin();
}
if(myTree !== undefined) {
$('#showCase').html(myTree.genHtml());
} else {
$('#showCase').html('tree deleted');
}
} catch (err) {
alert(err);
}
}
function UI() {
try {
$('#previous').html($('#showCase').html());
if(myTree === undefined) {
alert('empty tree');
return;
}
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();
myTree.depthFirstLog(callback);
alert(a);
alert(myTree.genHtml());
$('#showCase').html(myTree.genHtml());
} catch(err) {
alert(err);
}
}
function openWin() {
window.open("https://www.w3schools.com");
}
</script>
Node value:
<input type="text" name="fname" id = 'nodeValue' value="5" required></input>
<br/>
<div class="btn">
<button onclick="addNode()">Add value</button>
<button onclick="removeNode()">delete value</button>
<button onclick="removeMin()">delete Minimum</button>
<button onclick="UI()">depth first visit</button>
<button onClick="openWin()">show source code</button>
</div>
<br/>
<div id="showCase" class="wfm">now</div>
<br>
<div class="delimiter">previous step:</div>
<div id="previous" class="wfm">previous</div>
