问题标签 [subtree]

假设我有以下 XML ......

...返回“桶”包含“红色”和“蓝色”的 XPath 是什么？

我实际上是这个论坛的新手，我一直在尝试几天来找到一种将整个 LDAP 子树复制到另一棵树的简单方法。由于我找不到任何有用的东西，我也想在这里提出一个问题。有人知道如何以编程方式执行此操作吗？

对于添加、删除、搜索等正常操作，我一直在使用 Spring LDAP。

非常感谢 ！

我有一个单向的对象树，其中每个对象都指向它的父对象。给定一个对象，我需要获取它的整个后代子树，作为对象的集合。这些对象实际上不在任何数据结构中，但我可以轻松获得所有对象的集合。

天真的方法是检查批次中的每个对象，查看给定对象是否是祖先，然后将其放在一边。这不会太有效......它带有 O(N*N) 的开销，其中 N 是对象的数量。

另一种方法是递归方法，这意味着搜索对象的直接子级并重复该过程以进行下一个级别。不幸的是，树是单向的……没有直接接近孩子的方法，这只会比以前的方法稍微便宜一点。

我的问题：我在这里忽略了一个有效的算法吗？

谢谢，

尤瓦尔=8-)

这可能是一个简单的修复 - 但我试图将二叉搜索树上的所有节点（来自 Node 类的 Size 属性）相加。到目前为止，在我的 BST 类下面，我有以下内容，但它返回 0：

在我的 Node 类中，我有 Data ，它将 Size 和 Name 存储在它们的给定属性中。我只是想总结整个大小。有什么建议或想法吗？

我正在使用 Git 存储库来存储与我正在开发的网站相关的所有内容。该存储库包含与该站点相关的所有文件，包括文档、模型、原始分层图像等，以及我放在www子目录中的 Web 根目录。

我现在想开始将我选择使用的 CMS 与项目的其余部分集成；CMS 是一个开源项目，它也由 Git 管理（如果重要的话，托管在 GitHub 上）。显然 CMS 需要在www子目录中，但它不会是唯一的东西 - 会有 CSS 文件、图像、CMS 模板等等等。因此，我选择了使用子树合并策略将外部项目添加到我的存储库。因为我可能在某个时候想要修改原始项目，并回馈更改，所以我从 GitHub 克隆了 CMS 存储库，并从我的克隆中完成了子树合并。

问题是，外部项目（即CMS）有我想要包含的子模块。确保子模块集成到主项目中的最佳方法是什么？我是否必须为每个子模块进行子树合并？

我不太可能想要修改子模块，但我可能会修改一两个。

给定一个在坐标平面上相互连接的 n 个节点的图，找到包含 m 个节点的最小距离子树的最佳方法是什么？

我发现这个问题的唯一解决方案是生成要连接的节点的所有组合，并尝试通过 Kruskal 或 Prim 算法连接这些节点，同时忽略其余的，然后比较所有创建的树并找到最小的树，但是这个当涉及到较大的树木时，效率并不高。

有没有更快、更有效的算法/方法？

我有一个大的二叉树，T.T“匹配”。T 的一些子树也将匹配。事实上，匹配的子树甚至不需要是完整的子树：它们也可以被截断。通过截断子树，我的意思是子树中的节点可能不会一直包含子节点——一些有子节点的节点可能会删除它们的子节点。

一个例子：见这个链接。由poem1、stanza1、stanza2、line3 表示的树是截断子树的示例。

确定一棵树是否匹配需要对整棵树进行计算。这不是进步的。

我到底是如何找到所有匹配项的？

我有遥控器 Foo 和 Bar。Foo 是一个有很多目录的 Web 应用程序，其中相关的是/public包含各种文件和其他目录。

Bar 是一组库，没有在前端使用，因此，它应该/public/bar放在 Foo 中。Foo 那里没有文件。

无论是子模块还是子树合并，这都是小菜一碟。不过……</p>

Bar 的树很乱，它有各种预制作文件，如 PSD 和 FLA，其中唯一真正有用的部分是/www/tools.

所以，我想做的是将 Bar's 合并/www/tools到 Foo's/public/bar中，并假装 Bar 树的其余部分甚至不存在。

可以做？

（我想这与您从最初将您的项目合并为子树的项目合并的方式非常相似。我也不知道该怎么做。）

我们之前在主存储库中使用了许多子模块，但为了提高项目的可维护性，我们启动了一个实验分支，将它们全部替换为子树。

这很好用 - 但是现在当我尝试更新其中一个子树时，它错误地将更新合并到一个完全错误的目录中，甚至不是子树。

主存储库，其中分支“子树”包含实验分支，是：git://github.com/hugowetterberg/goodold_drupal.git

要合并更新的存储库来自：git://github.com/voxpelli/drupal-oembed.git

通过做合并：git merge -s subtree oembed/master

更新应合并到的路径：sites/all/modules/oembed/

它们合并到的路径：modules/aggregator/translations/

任何人都知道如何将更新放入子树或错误可能是什么？

我有一组树，其节点被标记（但不是唯一的）。具体来说，这些树来自一组已解析的句子（参见http://en.wikipedia.org/wiki/Treebank）。我希望从集合中提取最常见的子树——性能（还）不是问题。我会感谢算法（最好是 Java）或指向为树库执行此操作的工具的指针。请注意，子节点的顺序很重要。

编辑@mjv。我们在一个有限的领域（化学）中工作，它有一种程式化的语言，所以树木的种类并不多——可能类似于儿童读者。“猫坐在垫子上”的简单树。

这里句子包含两个相同的词性子树（实际标记“cat”。“mat”在匹配中并不重要）。所以算法需要检测到这一点。请注意，并非所有名词短语都是相同的——“the big black cat”可能是：

句子的长度会更长——在 15 到 30 个节点之间。我希望从 1000 棵树中获得有用的结果。如果这不会超过一天左右，那是可以接受的。

显然树越短越频繁，所以名词短语会很常见。

编辑如果这要通过展平树来解决，那么我认为它与最长公共子串有关，而不是最长公共序列。但请注意，我不一定只想要最长的 - 我想要一个足够长的列表以“有趣”（标准尚未确定）。