问题标签 [tree]

我有一个 xml 文档，其中包含一个类别列表：

以及产品清单：

如果产品的类别等于 12，则应将其转换为“配置/监视器/CRT 监视器”（取类别 12，然后它是父级 (13) 等）。如果 parent 为 0，则停止。

有没有一种优雅的方法可以使用 XSL 转换来做到这一点？

所以，我想出了这个方案，用于在多个线程同时具有读写访问权限的二叉树中旋转时锁定节点，这涉及每次旋转锁定四个节点，这似乎非常多？我想出了一种更聪明的方法，然后我想出了一种减少所需锁定的方法，但谷歌并没有出现太多（我可能使用了错误的术语）。

这是我目前的方案，橙色和红色节点被旋转移动或更改，需要锁定，绿色节点与任何受旋转影响但本身不受旋转影响的节点相邻。

二叉树旋转

我认为必须有一种更好的方法来做到这一点，我的一个想法是拍摄受影响的四个节点的快照，在快照中旋转它们，然后用快照替换当前节点（假设在我正在做旋转）-这将使我几乎可以无锁，但考虑到旋转是一个相当快速的操作（重新分配三个指针），我担心内存开销可能会很大？

我想我正在寻找如何有效地做到这一点的指针（没有双关语）。

我最近一直在使用嵌套集模型中的废话。我喜欢为几乎所有有用的操作和视图设计查询。我坚持的一件事是如何选择节点的直接子代（并且只有子代，而不是进一步的后代！）。

老实说，我确实知道一种方法 - 但它涉及无法管理的 SQL 数量。我确信有一个更直接的解决方案。

必须有一个标准的数据结构来保存例如狗的繁殖信息、植物遗传杂交和复杂的人际关系。

有人可能认为这将是一个简单的树形结构，但是每个后代的两个（或更多，对于基因工程）父母的组合，每个父母集多个不同的后代，父母的多次移动（种马与许多其他马交配），收养等使这成为一个非常分散的结构。

我希望有人以前解决过这个问题。我应该研究什么资源？

我不知道我的树会有多深。所以我认为 NSM 适合我，阅读一些文档。在 sql 中，此模型假设我使用整数值作为主键。我想创建一个双表只是为了存储通过与真实表一对一的关系连接的整数（PK，左，右）。事情变得复杂而且浪费空间磁盘，特别是当服务器不是我的并且我必须支付每兆字节时。帮助！！

更新

优秀的！太棒了！谢谢 Macka 和 Bill，我现在可以跳过阅读整本书。Celko 是亚马逊的未来订单。;-)

我在日常开发中处理了很多层次结构。Autodesk Maya 中的文件系统、嵌套 DAG 节点等。

我想知道，有没有专门设计用于遍历和比较对象层次结构的 Python 模块？

特别感兴趣的是在两个几乎相同的层次结构之间进行“模糊”比较的方法。这样做的一些原因是为了在 Maya 中匹配来自两个不同角色的两个节点层次结构，以便将动画从一个角色转移到另一个角色。

根据我一直在阅读的内容，我可能需要具有名称阈值的东西（我可以自己构建）来比较两个节点名称彼此之间的接近程度。然后，我需要一种方法来选择性地忽略子节点出现在层次结构中的顺序。最后，我需要处理深度阈值，以防节点可能在层次结构中略微向上或向下移动。

我有点需要决定这个，看看我是否能在我的学校项目截止日期前的几个小时内实现它，但我对数据结构不太了解，我需要建议......

我需要做两件事，他们可能会使用不同的数据结构。

1. 我需要一个数据结构来保存个人资料记录。个人资料必须可以按姓名和社会安全号码进行搜索。SSN 是独一无二的，所以我可能可以利用它来获得优势？我想哈希图是最好的选择吗？但是如何在哈希映射中使用 SSN 来利用它作为查找特定配置文件的优势？一个基本且易于理解的解释将不胜感激。

2. 我需要一个数据结构来保存有关城市的记录。我需要知道访问者最多的城市、访问量较少的城市以及访问特定城市的客户（从#1 中的数据结构中提取有关客户数据的配置文件）。

这是我的项目需要的第三个数据结构，它是我不知道从哪里开始的数据结构。如果可能，请提供有关使用哪种类型的数据结构的建议，并以粗体显示如何旧数据的示例。

注意：第一个数据结构已经完成（我在上一个问题
中谈到过）。第二个发布在 #1 上，尽管其他小组成员正在处理这个问题，但我只需要知道我们正在尝试做的是否是“最佳”方法。第三个是#2，我最需要帮助的那个。

我有一个本身具有树结构的表。

我想检索根节点下的整个子树。当我的根节点为“x”时，我想获取节点集 {1、5、6、7、10、11、12}。我怎样才能通过 linq 做到这一点？

我正在寻找一个好的数据结构来在树的节点上构建等价类。在理想的结构中，以下操作应该是快速的（O(1)/O(n)，视情况而定）并且容易（没有神秘代码段落）：

• (A) 从根部走树；在每个节点上 --> 子转换枚举子节点的所有等效版本
• (B) 合并两个等价类
• (C) 从现有节点（子节点）和其他数据的列表中创建新节点
• (D) 找到任何结构上与node 等价的节点（即它们有相同数量的子节点，对应的子节点属于同一个等价类，并且它们的“其他数据”相等），以便可以放入新的（或新修改的）节点在正确的等价类中（通过合并）

到目前为止，我已经考虑过（其中一些可以组合使用）：

• 冻糕，其中子代是对节点集合的引用，而不是对节点的引用。(A) 速度快，(B) 需要遍历树并更新节点以指向合并的集合，(C) 需要找到包含新节点的每个子节点的集合，(D) 需要遍历树
• 通过节点的特征维护节点的哈希。这使得 (D) 更快但 (B) 更慢（因为当等价类被合并时哈希必须被更新）
• 将节点串在一起形成一个循环链表。(A) 很快，(B) 会很快，但是事实上，将循环列表的一部分与自身“合并”实际上会拆分列表 (C) 会很快，(D) 需要遍历树
• 与上面类似，但在每个节点中都有一个额外的“向上”指针，可用于查找循环列表的规范成员。

我错过了一个甜蜜的选择吗？

我知道一个节点的程度是它拥有的孩子的数量。

但是，我们如何定义树的度数？