问题标签 [tree]

我正在做一个项目，它需要一个类别树，组织为 id、parent、title 表。在 Postgres 中检索类别及其子类别（以及完整的树，如果根类别的 parent=0）的最佳方法是什么？我正在寻找一个纯粹的数据库解决方案，但如果有一种适用于 Ruby 和 PHP 的方法 - 它也会很棒。

主要目标是选择子句的速度，因为此表中的数据对于更新/插入/删除速度并不重要。

UPD：还会有路径搜索，我的意思是从当前顶点（类别）到根类别的路径。

如何调整搜索树以处理有限的正则表达式？

给定一个文件名，我需要找到与该文件名匹配的所有节点。节点可能包含通常的文件名 glob（* 和？）。由于这是一棵搜索树，因此速度至关重要。

我应该补充一点，速度最重要的情况是排除比赛的平均时间。在大多数情况下，匹配会失败。

如果树包含以下节点：

• 搜索“foo”将返回节点 1 和 3。
• 搜索“bar”将返回节点 2 和 4。
• 搜索“fob”将不返回任何节点。
• 搜索“fooxbar”将返回节点 5。
• 搜索“foobar”将返回节点 3 和 4。

我正在考虑在我的应用程序中使用 PostgreSQL 的Ltree 模块来帮助处理线程注释。我一直在关注它用于线程评论。我认为它会在您需要更新节点及其子节点的情况下有所帮助，例如当您想要隐藏评论及其回复时。

我认为 ltree（或类似的东西）如果与传统的邻接列表（“comment_id”/“parent_comment_id”）结合使用会很有用。

在开始使用 ltree 之前，我想知道一些事情：

1. 您是否使用过 ltree？这就是所谓的“生产就绪”吗？
2. 如果是这样，你用它解决了什么问题？它做得好吗？
3. 你认为它适合线程评论系统吗？
   4. 如果你使用它，你在路径的“文本”部分使用了什么？您是否设置了类似于他们使用“Top.Astronomy.Cosmology”的 DMOZ 示例或基于主键“1.403.29.5”之类的东西？
   5. 有一个更好的方法吗？使用嵌套列表方法我有点紧张——我读过的所有内容都表明，UPDATES 或 INSERTS 并不是很热（你不需要重新排序吗？）。我也不是 CS 专业的，这种数据结构是我将来可能会忘记的东西。有人使用嵌套列表来发表评论或类似的东西吗？

如果有任何帮助，这是我正在考虑的架构：

ltree 使用的“路径”列看起来像：

在路径中使用主键有什么问题吗？我应该在路径中包含节点自己的主键吗？如果我这样做了，在其上放置一个唯一索引作为约束是否有意义？

我正在使用 MPTT 的模板标签来呈现我的流派树。

问题是，我的genre对象具有is_visible应该受到尊重的属性。

实现这一目标的最聪明、最干净的方法是什么？

附加信息

我需要正确生成 (X)HTML 列表嵌套。我已经定义了用于继承可见性检查的 SQL 函数。

并尝试覆盖full_tree_for_model标记以使其使用自定义管理器，这只是is_genre_branch_visible(genre_id)向 QuerySet 添加了额外的内容。但是订购出了点问题，无法真正弄清楚。

加它有效，但我不喜欢这种方法，对我来说感觉很丑。

我一直在寻找将 DAG 转换为树的 C# 示例。

有没有人有正确方向的例子或指示？

澄清更新

我有一个图表，其中包含我的应用程序需要加载的模块列表。每个模块都有一个它依赖的模块列表。例如这里是我的模块，A、BC、D 和 E

• A 没有依赖关系
• B 取决于 A、C 和 E
• C 取决于 A
• D 取决于 A
• E 取决于 C 和 A

我想解决依赖关系并生成一个看起来像这样的树......

- 一种

--+--B

-----+--C

---------+--D

--+--E

拓扑排序

感谢您提供的信息，如果我执行拓扑排序并反转输出，我将具有以下顺序

• 一种
• 乙
• C
• D
• 乙

我想维护层次结构，以便将我的模块加载到正确的上下文中，例如...模块 E 应该与 B 在同一个容器中

谢谢

罗汉

我使用了一个极简的 MVC 框架，其中PHP 控制器将DOM 模型交给XSLT 视图（cf okapi）。

为了构建导航树，我在 MYSQL 中使用了嵌套集。这样，我最终得到了一个如下所示的模型 XML：

它表示以下结构：

• 根
  • 电视
    • 管子
    • 液晶显示器
    • 等离子体
  • 便携式电子产品
    • MP3 播放器
      • 闪光
    • CD 播放器
    • 2路收音机

如何使用 XSLT 将此平面 XML 列表转换为嵌套的 HTML 列表？

PS：这是在 MySQL 中管理分层数据的示例树。

什么是 Splay 树、红黑树、AVL 树、B 树和 T 树？

我正在寻找好的实现。

我正在尝试从数据库中的表生成树结构。该表是扁平存储的，每条记录都有一个 parent_id 或 0。最终目标是生成一个选择框和一个节点数组。

我到目前为止的代码是：

它几乎可以工作，但不完全。谁能帮我完成它？

我想知道是否有人可以提供帮助。我的页面中的 HTML div 包含一个树控件，该控件根据用户按下的按钮显示或隐藏。该按钮触发一个 Ajax 事件，该事件在服务器上设置一个变量以显示或隐藏树，以便保持状态。

但这就是问题所在；重新显示树时，展开/折叠分支的图标不存在。到目前为止，我无法弄清楚为什么会这样。

树如下所示：第一个图形显示了应有的树，第二个图形显示了隐藏并重新显示后的树。

替代文字 http://www.dcs.bbk.ac.uk/~martin/Tree_with_icons.png 替代文字 http://www.dcs.bbk.ac.uk/~martin/Tree_without_icons.png

树的 HTML 作为列表构建在服务器上，每个列表项都有一个对 CSS 的类引用，如下所示：

任何人都可以建议在重新显示树时显示图标的方法吗？

我尝试在 div、内联 CSS 元素等中放置指向 CSS 文件的链接，但没有成功。

欢迎任何帮助。

我在运行时附上了树的 HTML 的摘录：

树本身位于一个名为“tree”的 div 中，它从 Javascript 方法更新如下：

树的Javascript是：

谢谢。

网页的Ajax如下图所示：

上面的 Ajax 是从具有三个按钮的表单触发的。“显示/隐藏”按钮可以查看事物；另外两个按钮也包含在一个 div 中，但它们没问题。

我正在做一个名为数据结构和算法的单元。我们刚刚开始，我的教授刚刚教给我们什么是代数语义以及什么是公理等基础知识。到目前为止，我只是以数组的形式使用树。不使用预排序树的签名作为树（值，树，树），其中值是节点中的值，左节点是第一棵树，右节点是第二棵树。

现在我将我的树定义为树（值，树，树）或 Nil，我不知道如何去定义 addNode（值，树）的代数。

每个级别都变得越来越复杂，另外，我无论如何都想不到一次扫描一个级别，现在已经尝试了一个小时。当我们沿着树向下走时，代数只是分支成越来越多的 if-else。我做对了吗？你能为我指出正确的方向吗？或者树不能实现为树（值，树，树）？

这是我教程的一部分（在附加问题中不值得任何标记），但我不是在寻找即时答案，我喜欢这个主题，并想了解更多。

编辑1：我查看了维基百科，我不想使用教科书来获得明确的答案，我只是在寻找正确方向的提示，无论我的方法是正确的还是完全不可能将树定义为树（值，树，树）。我知道您可以以列表的形式表示树 ADT。但我真的想好好想想。希望这是有道理的。非常感谢你们！

编辑2：嗯，很难通过互联网解释。假设我正在定义一个名为“树”的新数据结构。我可以以任何我想要的方式定义它，它必须表现得像一个平衡的二叉树（虽然，父母和孩子的值无关紧要）所以我将它定义为树：树（值，树，树）或无它不是编程代码，这就是我的定义。Tree 是一个值 + 2 棵其他树，或者 Tree 是 nil。现在 addNode(value, tree) 向树添加一个节点，同时仍然保持平衡。它不是编程代码，它只是代数语义。不知道能不能解释清楚。但是我找到了一个可以使用队列或堆栈实现的解决方案，但这是我必须定义的另一个 ADT，它是无效的。

编辑3：似乎我已经假设了许多使问题变得比实际应该更难的事情。首先，从我给出的一点解释来看，Gamecat 的回答是完美的。但我同意这些评论，包括其他 ADT 是完全有效的。事实上，当我们构建任何使用 Int 的东西时，我们正在为该结构使用 ADT。我认为每个 ADT 都必须是独一无二的。无论如何，非常感谢您的回答！