javascript - 如何在视觉上动态地重新定位二叉树节点

Question

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

现在剩下的唯一问题就是重新定位。原始代码完美地做到了这一点。但是因为我想要一棵二叉树，所以我让用户选择插入左 child 或右 child 。原始的重新定位代码使第一个子元素从父元素直接向下动画化，但这在二叉树中是错误的。我希望它向左或向右移动。

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]);
};

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

起初，这段代码似乎运行良好 ( /image/gjzOq.png )。但经过一些测试后，我发现重新定位存在一个巨大的问题:节点相互崩溃(/image/pdQfy.png)!

结论:我试图修改原始函数以考虑节点的左右定位，但无法做到。我写了这个方法的变体，但它仍然有一些问题，如图所示。如果您能就此事提供一些意见，我将不胜感激。

Answer 1

我最终快速解决了这个问题。

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