Built with blockbuilder.org
Last active
April 18, 2020 03:05
-
-
Save benlhy/2758784bd870864b27e92f0c5093a3aa to your computer and use it in GitHub Desktop.
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 = []; | |
} | |
function addRandomToTree() { | |
var randInt = Math.floor(Math.random() * 100); | |
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" , "white") | |
.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