Built with blockbuilder.org
forked from benlhy's block: animated binary tree
license: mit |
Built with blockbuilder.org
forked from benlhy's block: animated binary tree
<!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; | |
this.clearVisited() | |
while (true) { | |
node.visited = 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; | |
} | |
} | |
} | |
} | |
} | |
clearVisited() { | |
preorderTraverse_clear(this.root,[]) | |
} | |
} | |
class Node { | |
constructor(value, left = null, right = null,visited=true) { | |
this.left = left; | |
this.right = right; | |
this.value = value; | |
this.visited = visited; | |
} | |
} | |
const preorderTraverse_clear = (node, array) => { | |
if (!node) return array; | |
node.visited = false | |
array = preorderTraverse_clear(node.left, array); | |
array = preorderTraverse_clear(node.right, array); | |
return array; | |
}; | |
const preorderTraverse = (node, array, y, x, sign) => { | |
if (!node) return array; | |
if (y === 0) { | |
array.push({ value: node.value, y: 0, x: 0 ,visited:node.visited}); | |
} else { | |
x = x + (sign * 2) / Math.pow(2, y); | |
array.push({ value: node.value, y: y, x: x, visited:node.visited }); | |
} | |
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; | |
node.visited = item.visited; | |
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 link_sel = svg.append("g") | |
var node_sel = svg.append("g") | |
var keyFunc = function(d, i) { return d.value } | |
var visitedFunc = function(d,i) {return d.visited} | |
var nodes = node_sel | |
.selectAll("g") | |
.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("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 | |
var lastNumbers = [] | |
function addRandomToTree() { | |
tree.clearVisited(); | |
while(true){ | |
var randInt = Math.floor(Math.random() * 100); | |
if (!lastNumbers.includes(randInt)){ | |
newValue = randInt; | |
tree.add(randInt); | |
lastNumbers.push(randInt) | |
break; | |
} | |
} | |
//tree.clearVisited(); | |
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 = link_sel.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 = node_sel.selectAll("g") | |
.data(treeArray,keyFunc); | |
nodes.exit().remove() | |
var enter = nodes.enter().append('g') | |
.attr("transform",d => "translate(" + d.x + "," + d.y + ")"); | |
enter.append("circle") | |
.attr("fill" , d => !d.visited ? "grey" : d.value<newValue ? "#aec6cf" : d.value===newValue ? "white" : "#ff7560") | |
.attr("stroke" , "black") | |
.attr("r",0) | |
.transition() | |
.attr("r", 20) | |
enter.append("text") | |
.attr("text-anchor", "middle") | |
.attr("y", ".3em") | |
.text(d => d.value); | |
nodes = enter.merge(nodes); | |
*/ | |
var nodes = node_sel.selectAll("g") | |
.data(treeArray,d=>d); | |
nodes.exit().remove() | |
var enter = nodes.enter().append('g') | |
.attr("transform",d => "translate(" + d.x + "," + d.y + ")"); | |
enter.append("circle") | |
.attr("fill" , d => !d.visited ? "grey" : d.value<newValue ? "#aec6cf" : d.value===newValue ? "white" : "#ff7560") | |
.attr("stroke" , "black") | |
.attr("r", d => { | |
if(d.value==newValue){ | |
return 0 | |
} | |
else { | |
return 20 | |
} | |
}).transition() | |
.attr("r",20) | |
enter.append("text") | |
.attr("text-anchor", "middle") | |
.attr("y", ".3em") | |
.text(d => d.value); | |
nodes = enter.merge(nodes); | |
/* | |
nodes = node_sel | |
.selectAll("g") | |
.data(treeArray,d=>d.value) | |
nodes = nodes.enter().append() | |
console.log(nodes.nodes()) | |
var updated_nodes = nodes.selectAll("circle") | |
.attr("fill" , (d,i) => !d.visited ? "grey" : d.value<newValue ? "#aec6cf" : d.value===newValue ? "white" : "#ff7560"); | |
console.log(updated_nodes.nodes()) | |
*/ | |
} | |
</script> | |
</body> |