Built with blockbuilder.org
Last active
April 18, 2020 23:17
Star
You must be signed in to star a gist
animated binary tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
license: mit |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!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