家谱展示

Question

我正在创建一个家谱程序。我的问题是如何定位节点？最初，我将根节点定位在屏幕中心，如果它是完美的二叉树并且级别很少，则可以正常工作。然而，这通常不是情况。以下是一个示例树：

            A
        B       C
    D   E   F   I   J
K   L               N   O

正如您所看到的，主要问题是关于节点位置的。如果一个节点有许多子节点，而且它相邻的节点也有许多子节点，它们往往会重叠。(主要问题)我正在使用Silverlight中的Canvas绝对定位节点。如果您不是Silverlight开发人员，则可能不需要关注Silverlight和Canvas部分。我只需要了解如何定位节点的逻辑。

树的高度可以通过知道树的总层数来相对容易地计算出来，但是树的宽度是困扰我的问题。如何计算树的宽度（画布的总宽度）？

有人能给我一些关于如何设置画布宽度以及哪种逻辑对节点定位效果最好的一般性指导吗？

注意：我不是在要求整个算法，这也不是我的作业。我只需要节点定位部分的指导。

提前感谢 :)

- TCM

---

你能否澄清一下“画布的宽度”是什么意思？是指特定层级上节点的总数吗？ - Algorithmist

@Algorithmist：我的意思是画布宽度是树完全显示所需的水平显示区域。画布是我的树的容器(实际上你在其中显示)。它不是特定级别上节点总数，但你可以说是树的宽度。你可能认为它是任何特定宽度上最大节点数，但事实并非如此。例如，第5层可能有10个子节点，第6层只有4个子节点(第5层第1个节点和第10个节点各有2个子节点)，那么树的显示宽度就会不同。 - TCM

@Algorithmist：抱歉如果我表达不清楚。如果需要的话，我可以在纸上画图并上传图片，然后您可以查看链接以更好地理解。请告诉我。 - TCM

我们能否逐层遍历树，并检查节点是否有右或左子节点。针对每个节点，我们可以预留一定量的固定宽度（例如5个空格）。现在我们逐层遍历树，然后检查它是否有左或右子节点。如果假设某一层的第一个节点没有子节点，则我们可以将宽度设置为10。这是一个非常好的问题。我也在思考，看看资深程序员们有什么建议。 - Algorithmist

@Algorthmist：「真的是一个很好的问题」谢谢。 - TCM

Answer 1

如果您实现一个函数：width(node)，用于这棵树的任意节点，那么定位每个节点就很容易了。

这个函数可以递归定义：
- 对于高度为1的树，它正好是该节点的长度
- 对于高度大于1的树，它是该节点所有直接子节点的长度之和（加上它们之间的一些空格）。

- ninjaaa

Answer 2

我建议为了减少GUI的混乱，给予缩放功能。

一个有许多子节点的节点可以被分组，并且使用特殊图标表示，可以缩放到下一级，这样用户可以在家族成长时获得整体视图，然后可以缩放到任何他想要的分支。

可以从Google地图的UI中获取灵感，这可能会有所帮助。

- sashank

---

我很喜欢你的建议，但它并不完全是我想构建的。我正试图构建一个与myheritage.com完全相同的克隆网站。你可以去那里查看家谱树的构建过程，它非常美观 :) - TCM

为什么要完全克隆？给点新东西吧 ;) - sashank

首先让我基于他们的辛勤工作来构建他们所建立的东西。只有达到那个水平，我才能考虑给予额外的贡献 ;) - TCM

Answer 3

如果你想猜测画布的宽度，我建议从树的最宽层开始。你可以通过广度优先遍历计算出来。将该层节点数乘以每个节点所需的横向空间量，就可以得到所需的画布宽度。

然而，这并不能保证最宽层上相邻的节点不会各自有许多子节点。因此，为了实现无重叠的间距，首先要将树的叶子节点定位在最深的层，并向后遍历树，在上方添加父节点，并将叶子节点放入间隙和侧面。

- Eric Mickelsen

---

最宽的层级是我所需要的。最宽的层级指的是画布的宽度。但我们不能直接假设拥有最多节点的层级就是最宽的层级。你可以阅读我对Algorithmist的回复。例如，第五层可能有10个子节点，而第六层只有4个子节点（第五层的第一个节点有2个子节点，第五层的第十个节点也有2个子节点），那么树的显示宽度将会不同。 - TCM

从最深层开始定位树的叶子节点，然后向后遍历整棵树。这正是我所想的。但是在这里也存在一个问题。我应该将最深层的节点放在哪里？应该应用什么公式？ - TCM