如何最小化(二进制)搜索树的视觉宽度？

Question

介绍

我正在构建一个HTML5 Web应用程序,它从给定的数字列表中创建二叉搜索树的可视化表示.

目前,我有一个算法,根据树的最大深度(这是一个基数为0的值)计算每行节点之间的视觉间距:

offset = 50
offset *= pow(2, maxDepth - currentDepth)

从这里开始,使用该偏移量和其父节点的x位置确定节点的位置.

该算法运行良好,因为它始终能够适应任何深度的最宽树.然而,这也使得树有时不必要地宽.

例子

树枝向左(太宽):

树枝向左分支http://f.cl.ly/items/0c0t0L0L0o411h092G2w/left.png

树枝分叉到两侧(左侧和右侧可以更靠近在一起).

树枝分枝到两侧http://f.cl.ly/items/0r3X1j0w3r1D3v1V1V3b/left-right.png

理想情况下,上面的树应该像金字塔一样,宽度较小,边长,如下图所示:

平衡树(算法最佳的情况):

平衡树http://f.cl.ly/items/203m2j2i3P1F2r2T3X02/balanced.png

履行

属性

我正在使用Backbone.js从Node模型创建节点.每个节点都具有以下属性:

• parent(父节点)
• left(左子节点)
• 对(右子节点)
• x(节点的x位置,以像素为单位)
• y(节点的y位置,以像素为单位)

上面的x和y属性是根据节点分支的方向计算的:

if (parent.get('left') === node) {
    x = parentX - offsetX;
    y = parentY + offsetY;
} else if (parent.get('right') === node) {
    x = parentX + offsetX;
    y = parentY + offsetY;
}

此时,x和y属性是用于定位节点的确切值(每个节点都位于容器元素内的绝对值).

方法

• getDepth()(返回节点的base-0深度)
• getMaxDepth()(返回树中最后一行的深度)
• getRow(n)(返回深度为n的所有节点的数组)

题

因此,我的问题很简单:

什么是最小化二叉树美学宽度的最佳算法？

Answer 1

如果您查看类似问题的答案，它会对您有所帮助；它们包含指向完全执行您想要的树可视化类型的软件的链接。

审美是非常主观的，所以这只是我的看法。我认为我的指导方针（不是算法）如下。我假设子级的顺序很重要（因为它们是二叉搜索树）。

1. 只有x坐标才是有趣的；y坐标只能由节点的级别确定。（如果违反了这一点，我会觉得很难看，但正如我所说，口味不同。然而，其余的都是基于这个假设。）

2. 同一级别中的任何节点都不应该比某个固定的最小距离更近（例如D）。

3. 如果一个节点在x1和 处有两个子节点x2，我希望将其放置在 处(x1+x2)/2。在某些情况下，最好选择其他一些坐标[x1..x2]（可能是其末端之一）。我想可能存在一些不寻常的情况，外部坐标[x1..x2]会更好。

4. 如果一个节点有一个子节点 atx1且其父节点位于 处xp，我希望将其放置在 at (x1+xp)/2（这样它就位于连接其父节点和子节点的线上）。在某些情况下，最好偏离此并选择内部[xp..x1]（甚至外部）的其他坐标。

5. 我们将级别的宽度称为最左边和最右边节点之间的距离。最宽层的宽度应该最小。

这些准则所施加的限制无法同时满足。因此，你应该优先考虑它们，这又是主观的。例如，#4 和 #5 哪个更重要？你的 5 节点树草图意味着#4 更重要；如果#5更重要，你会得到一个类似房子的图片（垂直线）；如果两者都很重要，那么你现在的结果就很好了。

解决这个问题的一种方法是为指南分配权重，并定义不遵守这些指南的处罚。abs(x-(x1+x2)/2)例如，在准则 #3 中，如果父级的位置x不在其子级之间的中间位置，则可以进行惩罚；您还可以指定一个权重，告诉您与其他准则相比，该准则的重要性。然后，您应该尝试最小化解决方案的总加权惩罚。一般来说，这会给你一个约束优化问题，并且有多种方法可以解决此类问题。