<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/raphael/2.2.7/raphael.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/treant-js/1.0/Treant.js"></script>
<style>
/* required LIB STYLES */
/* .Treant se automatski dodaje na svaki chart conatiner */
.Treant { position: relative; overflow: hidden; padding: 0 !important; }
.Treant > .node,
.Treant > .pseudo { position: absolute; display: block; visibility: hidden; }
.Treant.Treant-loaded .node,
.Treant.Treant-loaded .pseudo { visibility: visible; }
.Treant > .pseudo { width: 0; height: 0; border: none; padding: 0; }
.Treant .collapse-switch { width: 3px; height: 3px; display: block; border: 1px solid black; position: absolute; top: 1px; right: 1px; cursor: pointer; }
.Treant .collapsed .collapse-switch { background-color: #868DEE; }
.Treant > .node img { border: none; float: left; }
</style>
<style>
/* optional Container STYLES */
.chart { height: 400px; width: 500px; margin: 5px; margin: 5px auto; border: 3px solid #DDD; border-radius: 3px; }
.node { color: #9CB5ED; border: 2px solid #C8C8C8; border-radius: 3px; }
.node p { font-size: 20px; line-height: 20px; height: 20px; font-weight: bold; padding: 3px; margin: 0; }
</style>
<br />
<div class="chart" id="OrganiseChart-simple">
</div>
<br/>
<div class="wfm" id="showCase"></div>
<script>
var simple_chart_config = {
chart: {
container: "#OrganiseChart-simple"
},
nodeStructure: {
text: { name: "Parent" },
children: [
{
text: { name: "left child" }
},
{
text: { name: "right child" }
}
]
}
};
</script>
<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, x) {
var instance = Object.create(BinarySearchTree.prototype);
instance.value = value;
instance.N = 1;
instance.right = undefined;
instance.left = undefined;
instance.color = x;
return instance
};
BinarySearchTree.prototype.insert = function (value) {
function rotateLeft(bst) {
var x = bst.right;
bst.right = x.left;
x.left = bst;
x.color = bst.color;
bst.color = 1;
x.N = bst.N;
bst.N = 1;
if(bst.left !== undefined) {
bst.N = bst.N + bst.left.N;
}
if(bst.right !== undefined) {
bst.N = bst.N + bst.right.N;
}
return x;
}
function rotateRight(bst) {
var x = bst.left;
bst.left = x.right;
x.right = bst;
x.color = bst.color;
bst.color = 1;
x.N = bst.N;
bst.N = 1;
if(bst.left !== undefined) {
bst.N = bst.N + bst.left.N;
}
if(bst.right !== undefined) {
bst.N = bst.N + bst.right.N;
}
return x;
}
function flipColors(bst) {
bst.color = 1;
bst.left.color = 0;
bst.right.color = 0;
}
function isRed(bst) {
if(bst === undefined) {
return 0;
}
return bst.color === 1;
}
function recurse(bst) {
if (bst === undefined) {
return BinarySearchTree(value, 1);
} else if (bst.value > value) {
bst.left = recurse(bst.left);
} else if (bst.value < value) {
bst.right = recurse(bst.right);
}
if(isRed(bst.right) && !isRed(bst.left)) {
bst = rotateLeft(bst);
}
if(isRed(bst.left) && isRed(bst.left.left)) {
bst = rotateRight(bst);
}
if(isRed(bst.left) && isRed(bst.right)) {
flipColors(bst);
}
bst.N = 1;
if(bst.left !== undefined) {
bst.N = bst.N + bst.left.N;
}
if(bst.right !== undefined) {
bst.N = bst.N + bst.right.N;
}
return bst;
}
return 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.rank = function (value) {
function recurse(bst) {
if(bst === undefined) return 0;
if (value < bst.value) {
return recurse(bst.left);
} else if (value > bst.value) {
if(bst.left !== undefined) {
return 1 + bst.left.size() + recurse(bst.right);
} else {
return 1 + recurse(bst.right);
}
} else {
if(bst.left !== undefined) {
return bst.left.size();
} else {
return 0;
}
}
}
return recurse(this);
}
BinarySearchTree.prototype.select = function (value) {
function recurse(bst) {
if(bst === undefined) return undefined;
var t = 0;
if(bst.left !== undefined) {
t = bst.left.size();
}
if (value < t) {
return recurse(bst.left);
} else if (value > t) {
value = value - t - 1;
return recurse(bst.right);
} else {
return bst;
}
}
return recurse(this);
}
BinarySearchTree.prototype.floor = function (value) {
function recurse(bst) {
if(bst === undefined) return undefined;
if (value === bst.value) {
return bst;
} else if (value < bst.value) {
return recurse(bst.left);
} else {
var t = recurse(bst.right);
if(t === undefined) {
return bst;
}
return t;
}
}
return recurse(this);
}
BinarySearchTree.prototype.ceiling = function (value) {
function recurse(bst) {
if(bst === undefined) return undefined;
if (value === bst.value) {
return bst;
} else if (value > bst.value) {
return recurse(bst.right);
} else {
var t = recurse(bst.left);
if(t === undefined) {
return bst;
}
return t;
}
}
return recurse(this);
}
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 rotateLeft(bst) {
var x = bst.right;
bst.right = x.left;
x.left = bst;
x.color = bst.color;
bst.color = 1;
x.N = bst.N;
bst.N = 1;
if(bst.left !== undefined) {
bst.N = bst.N + bst.left.N;
}
if(bst.right !== undefined) {
bst.N = bst.N + bst.right.N;
}
return x;
}
function rotateRight(bst) {
var x = bst.left;
bst.left = x.right;
x.right = bst;
x.color = bst.color;
bst.color = 1;
x.N = bst.N;
bst.N = 1;
if(bst.left !== undefined) {
bst.N = bst.N + bst.left.N;
}
if(bst.right !== undefined) {
bst.N = bst.N + bst.right.N;
}
return x;
}
function flipColors(bst) {
bst.color = 1;
bst.left.color = 0;
bst.right.color = 0;
}
function isRed(bst) {
if(bst === undefined) {
return 0;
}
return bst.color === 1;
}
function moveRedLeft(bst) {
//assuming that bst is red and both bst.left and bst.left.left are black,
//make bst.left or one of its children red.
flipColors(bst);
if(isRed(bst.right.left)) {
bst.right = rotateRight(bst.right);
bst = rotateLeft(bst);
}
return bst;
}
function deleteMin(bst) {
if(bst.left === undefined) return undefined;
if(!isRed(bst.left) && !isRed(bst.left.left)) {
bst = moveRedLeft(bst);
}
bst.left = deletMin(bst.left);
//bst.N = bst.N - 1;
//return balance(bst);
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 = '{';
function genHtml_F(bst, pos) {
function printNode() {
if(bst.color === 1) {
content += 'R ';
}
content += bst.value;
}
if(bst.left === undefined && bst.right === undefined) {
content += '"text": { "name": "'
printNode();
content += '" }';
return;
}
content += ' "text": { "name": "';
printNode();
content += '" }, "children": [';
if(bst.left !== undefined) {
content += '{';
genHtml_F(bst.left, 'left');
content += '}';
}
if(bst.left !== undefined && bst.right !== undefined) {
content += ',';
}
if(bst.right !== undefined) {
content += '{';
genHtml_F(bst.right, 'right');
content += '}';
}
content += ']';
}
genHtml_F(this, 'root');
content += '}';
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, 1);
} else {
myTree = myTree.insert(nodeVal);
}
myFunction();
//var str = myTree.genHtml();
//alert(str);
//$('#showCase').html(str);
} 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) {
myFunction();
//$('#showCase').html(myTree.genHtml());
} else {
$('#showCase').html('tree deleted');
}
} catch (err) {
alert(err);
}
}
function rankNode() {
try {
var nodeVal = document.getElementById('nodeValue').value;
nodeVal = parseInt(nodeVal);
if(myTree !== undefined) {
alert(myTree.rank(nodeVal));
} else {
$('#showCase').html('tree deleted');
}
} catch (err) {
alert(err);
}
}
function selectNode() {
try {
var nodeVal = document.getElementById('nodeValue').value;
nodeVal = parseInt(nodeVal);
if(myTree !== undefined) {
if(myTree.select(nodeVal) === undefined) {
alert("not found");
} else {
alert(myTree.select(nodeVal).value);
}
} else {
$('#showCase').html('tree deleted');
}
} catch (err) {
alert(err);
}
}
function floorNode() {
try {
var nodeVal = document.getElementById('nodeValue').value;
nodeVal = parseInt(nodeVal);
if(myTree !== undefined) {
if(myTree.floor(nodeVal) === undefined) {
alert("not found");
} else {
alert(myTree.floor(nodeVal).value);
}
} else {
$('#showCase').html('tree deleted');
}
} catch (err) {
alert(err);
}
}
function ceilingNode() {
try {
var nodeVal = document.getElementById('nodeValue').value;
nodeVal = parseInt(nodeVal);
if(myTree !== undefined) {
if(myTree.ceiling(nodeVal) === undefined) {
alert("not found");
} else {
alert(myTree.ceiling(nodeVal).value);
}
} else {
$('#showCase').html('tree deleted');
}
} catch (err) {
alert(err);
}
}
function sizeNode() {
try {
if(myTree !== undefined) {
alert(myTree.size());
} 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) {
myFunction();
//$('#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);
} catch(err) {
alert(err);
}
}
function openWin() {
window.open("https://xyzcode.blogspot.com/2018/02/how-to-build-binary-search-tree-with.html");
}
</script>
<script>
var my_chart = new Treant( simple_chart_config );
</script>
<script>
function myFunction() {
var myString = myTree.genHtml();
var obj = JSON.parse(myString);
simple_chart_config.nodeStructure = obj;
my_chart.destroy()
my_chart = new Treant(simple_chart_config, null, $);
}
</script>
Node value:
<input type="text" name="fname" id = 'nodeValue' value="50" required></input>
<br/>
<div class="btn">
<button onclick="addNode()">Add value</button>
<button onclick="sizeNode()">size</button>
<button onclick="rankNode()">rank</button>
<button onclick="selectNode()">select</button>
<button onclick="floorNode()">floor</button>
<button onclick="ceilingNode()">ceiling</button>
<button onclick="UI()">depth first visit</button>
<button onClick="openWin()">show source code</button>
</div>
<br/>
<div id="showCase" class="wfm"></div>
<br>
