Algorithm
Given a tree structure . First, we start indexing each node of the tree with following rules:
Traverse using Depth-First-Search (DFS)
The first child of a node has same index with its parent’s
Source code
updateIndex() {
for (let i = 0; i < this.children.length; i++) {
// first child has the same index with its parent's
// then increase from that
if (i > 0) TreeNode.nIdx++;
this.children[i].index = TreeNode.nIdx;
// DFS
this.children[i].updateIndex(TreeNode.nIdx);
}
}
Second, we adjust node’s position based on each node’s index:
DFS traversing
If the traversing node is a leaf, then:
Else:
Source code
layout(hMargin = 25, vMargin = 25) {
this.y = this.level * hMargin;
if (this.children.length > 0) {
for (let i = 0; i < this.children.length; i++) {
this.children[i].layout();
}
this.x = (this.children[0].x + this.children[this.children.length - 1].x) / 2;
} else {
this.x = this.index * vMargin;
}
}