问题标签 [tree]

给定一个简单的 (id, description) 表 t1，例如

还有一个父子关系表t2，比如

Oracle 提供了一种将其作为具有一些自定义语法扩展的树来遍历的方法：

确切的语法并不重要，我可能在上面犯了一个错误。重要的是上面会产生一些看起来像

我的问题是：是否可以在 sys_connect_by_path() 中加入另一个表，例如上面的 t1 表，以生成类似：

我正在尝试确定一种存储一组对象的快速方法，每个对象都有一个 x 和 y 坐标值，以便我可以快速检索某个矩形或圆形内的所有对象。对于小型对象集（约 100 个），简单地将它们存储在列表中并遍历它的简单方法相对较快。然而，对于更大的群体来说，这预计会很慢。我也尝试将它们存储在一对 TreeMaps 中，一个按 x 坐标排序，一个按 y 坐标排序，使用以下代码：

这也有效，并且对于较大的对象集更快，但仍然比我想要的慢。部分问题还在于这些对象四处移动，并且需要重新插入此存储中，这意味着将它们从树/列表中删除并重新添加到树/列表中。我不禁认为那里必须有更好的解决方案。我正在用 Java 实现它，如果它有什么不同的话，尽管我希望任何解决方案都将以有用的模式/算法的形式出现。

我需要一个像这样的树/有向无环图实现：

• 没有任何类型的排序。
• 这TreeNode只是键和可能值的包装器（节点不必设置值）。
• 我需要链接到父母和孩子。

标准 API 或 Commons 等中是否有任何东西可以为我做到这一点？

我不介意自己写（我当然不会要求你们这样做）我只是不想重新发明轮子。

好奇什么被认为是判断有向无环图强度的可靠算法/方法 - 特别是某些节点的强度。我对此的主要问题可以归结为以下两个图表：

（如果图表未显示，请单击此处或访问此链接：http ://www.flickr.com/photos/86396568@N00/2893003041/

在我看来，A 的地位比 A 强。我判断强度的依据是如果一个链接被击倒，一个节点可以保持多强。我称第一个为细“高跷”，第二个为粗“茎”。

以下是我目前考虑的判断节点强度的方法：

1）计算下面的节点数，减去上面的节点数。

• A=7, a=7, B=5, b=1

2）计算每个节点的完整路径（到终止）的数量，将它们的长度相加。

• A=17 (1+5+5+5+1), B=12 (4+4+4), a=9 (3+3+3), b=2
• 这使高跷更坚固，而不是茎。

3）计算每条可能的路径，将每个节点视为目的地。

• A=9 (A->B, A->C, A->D, A->E, A->G, 2xA->F, 2xA->H), B=6, a=9, b= 2

到目前为止，3 似乎是最好的选择，但有没有更好的、适用于 DAG 的通用选项？这是具有已知最佳方法的东西吗？原则是在图表中使用尽可能多的信息，并以直观的方式解释解决方案。

我有一种树结构，表示地图中的层层次结构，按层和类别的类型划分。每个节点可以是不同类型的层的不同类（但所有节点都实现一个公共接口）。

我需要将该类转换为 ASP.NET TreeView 控件。输入树中的每个节点都是输出树中的一个节点，其属性集取决于节点的类型。我不希望输入树类知道 UI 类，所以我不能在其中编写“ToTreeViewNode()”方法。目前有 4 种具体节点类，其中 2 种是复合的（包含子节点），其中 2 种是叶子。这在未来可能会改变。

感觉这里有一种设计模式很想用，你能帮我看看它是什么吗？

我想知道是否有人可以推荐一个好的 C++ 树实现，如果可能的话，希望它是兼容 stl 的。

作为记录，我以前写过很多次树算法，我知道这很有趣，但如果可能的话，我想变得务实和懒惰。因此，与工作解决方案的实际链接是这里的目标。

注意：我正在寻找通用树，而不是平衡树或地图/集，在这种情况下，结构本身和树的连接性很重要，而不仅仅是其中的数据。所以每个分支都需要能够保存任意数量的数据，并且每个分支都应该是可单独迭代的。

我有一个带有专辑的 mysql 表。每个相册可以是顶级相册，也可以是另一个相册的子相册。每个相册都有一个文件夹名称，它是其图片所在文件夹的名称。每个相册还有一个名为 parent 的字段，它是父相册的 id。所以，如果我有这样的图像路径：

那么数据库中的专辑表将如下所示：

那么问题来了，如何仅使用 mysql 从该表中获取先前打印的路径？

今天早些时候我在想一个小游戏的想法，偶然发现了如何实现它。这个想法是，玩家可以做出一系列动作，产生一点影响，但如果按照特定的顺序进行会产生更大的影响。到目前为止一切顺利，我知道该怎么做。显然，我必须让它变得更复杂（因为我们喜欢让它更复杂），所以我认为序列可能有不止一种可能的路径，它们都会产生更大的影响，尽管是不同的。此外，某些序列的一部分可能是其他序列的开始，甚至整​​个序列可能包含在其他更大的序列中。现在我不确定实现这一点的最佳方法。不过，我有一些想法。

1）我可以实现一个循环n链表。但是由于移动列表永远不会结束，我担心它可能会导致堆栈溢出™。这个想法是每个节点都会有 n 个子节点，并且在收到命令后，它可能会将您带到他的一个子节点，或者，如果没有子节点可用于该命令，则将您带回到起点。到达任何孩子时，都会执行几个功能，从而产生大小影响。但是，这可能会导致树上出现许多重复的节点，以应对所有可能以该特定动作结束并具有不同效果的序列，这可能很难维护，但我不确定。我从来没有在代码上尝试过这么复杂的东西，只是理论上。这个算法是否存在并且有名字？这是个好主意吗？

2）我可以实现一个状态机。然后，我不会在链表中徘徊，而是有一些巨大的嵌套开关来调用函数并相应地更新机器状态。似乎实现起来更简单，但是......好吧......看起来并不有趣......也不优雅。巨型开关在我看来总是丑陋，但这会更好吗？

3) 建议？我很好，但我很缺乏经验。编码领域的好处是，无论你的问题多么奇怪，过去有人解决了它，但你必须知道去哪里找。有人可能有比我更好的主意，我真的很想听听建议。

假设您有一个存储有序树层次结构的平面表：

这是一个图表，我们有[id] Name. 根节点 0 是虚构的。

您将使用什么简约方法将其作为正确排序、正确缩进的树输出到 HTML（或文本）？

进一步假设你只有基本的数据结构（数组和哈希图），没有带有父/子引用的花哨对象，没有 ORM，没有框架，只有你的两只手。该表表示为一个结果集，可以随机访问。

伪代码或纯英文都可以，这纯粹是一个概念问题。

额外的问题：有没有更好的方法在 RDBMS 中存储这样的树结构？

编辑和添加

回答一位评论者（Mark Bessey）的问题：根节点不是必需的，因为它永远不会被显示。ParentId = 0 是表达“这些是顶级”的约定。Order 列定义了如何对具有相同父节点的节点进行排序。

我所说的“结果集”可以被描绘成一个哈希图数组（保留在那个术语中）。因为我的例子本来就应该在那里。有些答案会加倍努力并首先构建它，但这没关系。

树可以任意深。每个节点可以有 N 个孩子。不过，我并没有完全想到“数百万个条目”树。

不要将我选择的节点命名（'Node 1.1.1'）误认为是可以依赖的东西。这些节点同样可以称为“Frank”或“Bob”，没有暗示命名结构，这只是为了使其可读。

我已经发布了我自己的解决方案，因此你们可以将其分解。

当我提到嵌套集模型时，我指的是这里描述的内容。

我需要构建一个新系统，用于在用户定义的层次结构中存储“类别”（我想不出更好的词来形容它）。由于嵌套集模型针对读取而不是写入进行了优化，因此我决定使用它。不幸的是，在我对嵌套集的研究和测试过程中，我遇到了如何显示带有排序节点的层次树的问题。例如，如果我有层次结构：

我希望对其进行排序，使其显示为：

请注意，制造出现在研究之前。

无论如何，经过长时间的搜索，我看到了诸如“将树存储在多维数组中并对其进行排序”和“将树重新排序并序列化回您的嵌套集合模型”之类的答案（我在解释......）。无论哪种方式，第一个解决方案都是对 RAM 和 CPU 的可怕浪费，它们都是非常有限的资源……第二个解决方案看起来像是很多痛苦的代码。

无论如何，我能够弄清楚如何（使用嵌套集模型）：

1. 在 SQL 中启动新树
2. 插入一个节点作为树中另一个节点的子节点
3. 在树中的兄弟节点之后插入一个节点
4. 从 SQL 中拉出具有层次结构的整个树
5. 从层次结构中的特定节点（包括根节点）拉取子树，有或没有深度限制
6. 查找树中任何节点的父节点

所以我想#5 和#6 可以用来做我想要的排序，它也可以用来按排序顺序重建树。

然而，现在我已经查看了所有这些我学会做的事情，我发现#3、#5 和#6 可以一起使用来执行排序插入。如果我做了排序插入，它总是被排序。但是，如果我改变了排序标准或者我想要一个不同的排序顺序，我就会回到原点。

这可能只是嵌套集模型的限制吗？它的使用是否会抑制输出的查询排序？