Skip to content

Instantly share code, notes, and snippets.

@benlhy
Last active April 18, 2020 23:17
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save benlhy/83a93740449b29ab731184bd233c9994 to your computer and use it in GitHub Desktop.
animated binary tree
license: mit
<!DOCTYPE html>
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src=https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js></script>
<style>
body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
svg {width:100%;height:100%}
</style>
</head>
<body>
<button type="button" onclick="addRandomToTree()">Add node</button>
<button type="button" onclick="resetTree()">Reset</button>
<script>
// Feel free to change or delete any of the code you see in this editor!
var width = 600;
var height = 600;
var margin = { top: 20, bottom: 20, left: 40, right: 20 };
class Tree {
constructor() {
this.root = null;
}
toObject() {
return this.root;
}
add(num) {
if (!this.root) {
this.root = new Node(num);
} else {
let node = this.root;
while (true) {
if (num < node.value) {
if (node.left) {
node = node.left;
} else {
node.left = new Node(num);
return;
}
} else {
if (node.right) {
node = node.right;
} else {
node.right = new Node(num);
return;
}
}
}
}
}
}
class Node {
constructor(value, left = null, right = null) {
this.left = left;
this.right = right;
this.value = value;
}
}
const preorderTraverse = (node, array, y, x, sign) => {
if (!node) return array;
if (y === 0) {
array.push({ value: node.value, y: 0, x: 0 });
} else {
x = x + (sign * 2) / Math.pow(2, y);
array.push({ value: node.value, y: y, x: x });
}
y = y + 1;
array = preorderTraverse(node.left, array, y, x, -1);
array = preorderTraverse(node.right, array, y, x, 1);
return array;
};
const preorderTraverse_link = (node, linkarray, y, x, sign) => {
if (!node) return linkarray;
var prev_x = x;
var prev_y = y - 1;
if (y === 0) {
} else {
x = x + (sign * 2) / Math.pow(2, y);
linkarray.push({ source: [prev_x, prev_y], target: [x, y] });
}
y = y + 1;
linkarray = preorderTraverse_link(node.left, linkarray, y, x, -1);
linkarray = preorderTraverse_link(node.right, linkarray, y, x, 1);
return linkarray;
};
var topMargin = 50;
const convertToXY = (item) => {
var node = {};
node.value = item.value;
node.y = item.y * 50 + topMargin;
node.x = item.x * 200 + 400;
return node;
};
const convertLinkToXY = (item) => {
var node = { source: [], target: [] };
node.source[0] = item.source[0] * 200 + 400;
node.source[1] = item.source[1] * 50 + topMargin;
node.target[0] = item.target[0] * 200 + 400;
node.target[1] = item.target[1] * 50 + topMargin;
return node;
};
let tree = new Tree();
tree.add(50);
/*
tree.add(4);
tree.add(3);
tree.add(8);
tree.add(2);
tree.add(1);
tree.add(9);
tree.add(7);
*/
var treeArray = preorderTraverse(tree.root, [], 0, 0, 1);
//var treelinkArray = preorderTraverse_link(tree.root, [], 0, 0, 1);
treeArray = treeArray.map(convertToXY);
//treelinkArray = treelinkArray.map(convertLinkToXY);
// Feel free to change or delete any of the code you see in this editor!
var svg = d3
.select("body")
.append("svg");
/*
svg.selectAll("path")
.data(treelinkArray)
.enter()
.append("path")
.attr("d", linkGen)
.attr("fill", "none")
.attr("stroke", "black");
*/
var nodes = svg.append("g")
.attr("class", "nodes")
.selectAll("circle")
.data(treeArray)
.enter()
// Add one g element for each data node here.
.append("g")
// Position the g element like the circle element used to be.
.attr("transform",d => "translate(" + d.x + "," + d.y + ")");
nodes.append("circle")
.attr("class", "node")
.attr("fill" , "white")
.attr("stroke" , "black")
.attr("r", 20);
// Add a text element to the previously added g element.
nodes.append("text")
.attr("text-anchor", "middle")
.attr("y", ".3em")
.text(d => d.value);
var linkGen = d3.linkVertical();
var prevLink=[]
function resetTree() {
tree = new Tree();
tree.add(50);
var treeArray = preorderTraverse(tree.root, [], 0, 0, 1);
var treelinkArray = preorderTraverse_link(tree.root, [], 0, 0, 1);
treeArray = treeArray.map(convertToXY);
var treelinkArrayBef = treelinkArray.map(convertLinkToXY);
var treelinkArrayAft = treelinkArray.map(convertLinkToXY);
updateTree(treeArray,treelinkArrayBef,treelinkArrayAft);
prevLink = [];
}
var newValue = 0
function addRandomToTree() {
var randInt = Math.floor(Math.random() * 100);
newValue = randInt
tree.add(randInt);
var treeArray = preorderTraverse(tree.root, [], 0, 0, 1);
var treelinkArray = preorderTraverse_link(tree.root, [], 0, 0, 1);
treeArray = treeArray.map(convertToXY);
var treelinkArrayAft = treelinkArray.map(convertLinkToXY);
var treelinkArrayBef = treelinkArray.map(convertLinkToXY);
//var treelinkArrayBef = treelinkArrayAft;
console.log("Before:")
console.log(treelinkArrayBef)
console.log("Aft")
console.log(treelinkArrayAft)
var mydiff = _.cloneDeep(_.differenceWith(treelinkArrayBef,prevLink,_.isEqual))
console.log(mydiff)
prevLink = _.cloneDeep(treelinkArrayBef)
for (let i = 0;i<prevLink.length;i++){
if(_.isEqual(prevLink[i].source,mydiff[0].source) && _.isEqual(prevLink[i].target,mydiff[0].target) )
prevLink[i].target = prevLink[i].source
}
//prevLink = [{"source":[400,50],"target":[400,50]}]
updateTree(treeArray,prevLink,treelinkArrayBef);
prevLink = _.cloneDeep(treelinkArrayBef);
}
function updateTree(treeArray,treelinkArrayBef,treelinkArrayAft){
var t = d3.transition()
.duration(750)
var links = svg.selectAll("path")
.data(treelinkArrayBef);
var enter_links = links.enter().append("path")
.attr("fill", "none")
.attr("stroke", "black")
;
links = enter_links.merge(links)
.attr("d", linkGen);
links = svg.selectAll("path")
.data(treelinkArrayAft);
links.exit().remove();
enter_links = links.enter().append("path")
.attr("fill", "none")
.attr("stroke", "black");
links = enter_links.merge(links)
.transition()
.attr("d", linkGen);
var nodes = svg.append("g").selectAll('circle')
.data(treeArray);
svg.selectAll("g").selectAll('g').data(treeArray).exit().remove()
var enter = nodes.enter().append('g')
.attr("transform",d => "translate(" + d.x + "," + d.y + ")");
enter.append("circle")
.attr("class", "node")
.attr("fill" , d => d.value<newValue ? "#aec6cf" : d.value===newValue ? "white" : "#ff7560")
.attr("stroke" , "black")
.attr("r", 20);
enter.append("text")
.attr("text-anchor", "middle")
.attr("y", ".3em")
.text(d => d.value);
nodes = enter.merge(nodes);
}
/*
const mytree = {
value: 3,
left: {
value: 1,
left: null,
right: {
value: 2,
left: null,
right: null
}
},
right: {
value: 7,
left: {
value: 4,
left: null,
right: {
value: 6,
left: {
value: 5,
left: null,
right: null
},
right: null
}
},
right: {
value: 10,
left: {
value: 9,
left: {
value: 8,
left: null,
right: null
},
right: null
},
right: null
}
}
};
var dataset = [
{ value: 3, y: 50, x: 400 },
{ value: 1, y: 100, x: 200 },
{ value: 2, y: 150, x: 300 },
{ value: 7, y: 100, x: 600 },
{ value: 4, y: 150, x: 500 },
{ value: 6, y: 200, x: 550 },
{ value: 5, y: 250, x: 525 },
{ value: 10, y: 150, x: 700 },
{ value: 9, y: 200, x: 650 },
{ value: 8, y: 250, x: 625 }
]
var multiLinkData = [
{ source: [ 400, 50 ], target: [ 200, 100 ] },
{ source: [ 200, 100 ], target: [ 300, 150 ] },
{ source: [ 400, 50 ], target: [ 600, 100 ] },
{ source: [ 600, 100 ], target: [ 500, 150 ] },
{ source: [ 500, 150 ], target: [ 550, 200 ] },
{ source: [ 550, 200 ], target: [ 525, 250 ] },
{ source: [ 600, 100 ], target: [ 700, 150 ] },
{ source: [ 700, 150 ], target: [ 650, 200 ] },
{ source: [ 650, 200 ], target: [ 625, 250 ] }
];
svg.selectAll('path')
.data(pathData)
.enter()
.append('path')
.attr('d', pathData)
.attr('fill', "none")
.attr('stroke','black');*/
/*
var circles = svg
.selectAll("circle")
.data(dataList)
.enter()
.append("circle")
.attr("r", (d) => 20)
.attr("cx", (d) => 100)
.attr("cy", (d) => 100)
.attr("stroke", "grey")
.attr("fill", "white")
.text((d) => d);
var texts = svg
.selectAll("text")
.data(dataList)
.enter()
.append("text")
.attr("x", 100)
.attr("y", 100)
.text((d) => d);*/
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment