如何直观地动态重新定位二叉树节点

Question

我一直在使用以下代码：http://bl.ocks.org/NPashaP/7683252。这是树的图形表示。我剥离了大部分代码(优雅标签)，每个父级只允许两个节点，并将数据结构更改为数组。

现在剩下的唯一问题是重新定位。原始代码完美地做到了这一点。但是由于我想要一个二叉树，我让用户选择插入一个左子项或右子项。原始重新定位代码将第一个子项从父级直接向下激活，但这在二叉树中是错误的。我希望它要么向左，要么向右。

reposition = function (v) {
function repos(v) {
var lC = getLeafCount(v.v),
left = v.p.x; //parent's x-position
v.c.forEach(function (d) {
var vc = d; //saving reference of the child in parent object
d = tree.getVerticeById(d.v); //actually fetching the child object
var w = 0;
if(d.d == 'right') { w += 15 * lC }
if(d.d == 'left') { w -= 15 * lC }
d.p = {x: left + w, y: v.p.y + tree.h}; //setting the position
vc.p = d.p; //setting the child's pos in parent obj
repos(d);
});
}
repos(v[0]);
};

我的代码的某些部分与原始代码不同，因为我如前所述更改了数据结构。我试图评论可能令人困惑的部分，但重要的是重新定位的数学。

起初，这段代码似乎运行良好(https://i.stack.imgur.com/gjzOq.png)。但是经过一些测试，我发现了重新定位的巨大问题：节点相互崩溃(https://i.stack.imgur.com/pdQfy.png)！

结论：我曾尝试修改原始函数以牢记节点的左右定位，但无法做到。我写了这种方法的变体，但它仍然存在一些问题，如图所示。我将感谢对此事的一些投入。

Answer 1

我最终对这个问题做了一个快速修复。

运行问题中发布的重新定位功能后，我运行了另一个解决问题的功能。新函数遍历树的所有级别，并检查节点是否靠得太近。如果是，则算法会找到最接近的共同祖先，并增加其左右子项之间的距离。在此之后，节点之间不再发生冲突。