绘制分层树形结构：树状图

Question

我正在尝试开发一个层次树的视图，其中每个节点的权重是它实际拥有的子节点数量。叶节点的权重为1。

我想以一种方式排列这些项，使得可以通过显示根类别（没有父节点）来浏览更深入树形结构。单击节点会使视图重新绘制，只显示该节点的子节点。

棘手的部分是节点的像素大小应该与相邻节点的权重成比例。根据维基百科，这称为treemapping，我需要的是一种平铺算法，我试图自己弄清楚，但似乎比我预期的要复杂。

举个例子，Mac Os X上有一个名为GrandPerspective的程序，显示您HD的文件夹大小：

_{(来源: arstechnica.com)}

我想以这种方式排列节点！（当然，大小与文件夹大小成比例）

有什么建议吗？

谢谢

- Jack

Answer 1

在您展示的文件系统示例中使用的数据结构很可能是KD树。我不确定您想要解决的问题在多大程度上与文件系统示例相匹配，但这是我自己解决文件系统案例的方法：

您从表示硬盘根目录的矩形开始。您获取目录中的所有文件和目录，并为它们分配大小。

1. 对于文件，大小为文件的大小
2. 对于目录，大小为其包含的所有文件的完整大小（包括其所有子文件夹及其子文件夹等）。

现在，您尝试将此列表切成两个尽可能相等的列表。现在，您将输入矩形切成两个矩形，其大小比例与您切割输入文件的两个列表相同。您应该沿着较短的输入矩形大小的轴进行切割，以确保始终具有尽可能正方形的矩形。现在，您在其相应的矩形上递归地运行两个列表的算法。

基本情况如下：

1. 列表中只有一个文件。然后，您将使用文件类型的颜色填充矩形。
2. 列表中只有一个目录。对于这种情况，您需要在矩形内部的目录内容上递归运行算法。

选择如何将列表分成尽可能相等的两部分可能并不容易（这是一个背包问题吗？）。一个不错的启发式方法可能是按降序对列表进行排序，并从列表中取出元素并将其放入当前最小的两个结果列表之一。

编辑：拆分问题称为划分问题，是背包问题的特殊情况。在SO上，这个主题被讨论了。

- Laserallan

---

好的，也许我放的截图有误导性，因为我不想用它来处理文件，而是用于其他类似的分层数据结构。是的，我认为这是一种背包问题，所以我想知道应该选择哪种算法，这种分治方法可能有效...我会尝试并告诉你结果（如果看起来合理就接受它），谢谢！ - Jack

添加了一些列表分割部分的信息。事实证明，它是NP完全问题，但可以使用启发式方法解决您的实例。 - Laserallan

刚刚尝试了贪心算法，看起来效果不错，谢谢！ - Jack

Answer 2

那是一个方形树状图。您可以阅读解释此技术的论文。

- tkerwin