问题标签 [subtree]

我需要以以下（奇怪的）方式创建一个二叉搜索树：

我得到一个数组（A[n]）。A[1] 成为树的根。

• 然后，我将 A[1]+A[2] 插入到根的左子树（subtree1，下面使用），并将 A[1]-A[2] 插入到根的右子树（subtree2）。

• 我将 A[1]+A[2]+A[3] 插入 subtree1 (subtree3) 的左子树，将 A[1]+A[2]-A[3] 插入 subtree1 (subtree4) 的右子树。

• 然后，我将 A[1]-A[2]+A[3] 插入到 subtree2 (subtree5) 的左子树和 A[1]-A[2]-A[3] 到 subtree2 (subtree6) 的右子树）。

• 我对 subtree3、subtree4、subtree5、subtree6 重复，直到到达数组的末尾。

所以，基本上，数组的第一个元素成为树的根，然后我向下移动：每个左子树的值都是其父元素加上数组的下一个元素的总和，每个右子树的值都是它的父元素和数组中的下一个元素。

我知道我需要使用递归的概念，但要以一种修改的方式。在这里输入我的问题并试图向除了我的大脑之外的其他人解释它实际上使我形成它的方式给了我一些尝试的想法但我可以看到我正在处理的问题是一个常见的问题所以也许你可以给我对如何使用递归来构建树的一些指示。

环顾其他问题和讨论，我知道有一项反对提出完整解决方案的政策，所以我想明确表示我不是在寻求解决方案，而是寻求指导。如果有人想看看我可以告诉你我已经做了什么。

在我的项目中，我有 3 个子目录，其中包含由子树策略合并的库项目。假设我签出 master分支并在主项目和库文件中进行更改。我无法签出任何 lib 分支，因为我将丢失本地更改。在一个分支中运行stash并将其应用于另一个分支不是一个好主意。

如何仅使用标准 git 工具（没有任何 git-subtree 包）拆分更改并将其提交到正确的分支中？？？

目前我正在为最后一个学期做我的项目/论文，我想在“检测网络中的网页变化”上做这件事。我已经阅读了两篇关于这个主题的论文，但我有一些困惑

1.在一篇题为

一种增强的网页变化检测算法及应用加速移动网页转码1

这个已经写完了

首先从 HTML 文档生成子树，其中每个子树根据其标记内容被赋予一个标记。

我的问题是如何从 HTML 文档生成子树？这样做的技术是什么。下一个问题是“根据标签内容打分”是什么意思。

2.请看这里的图片！！拟议方法的总图

在“计算最相似的子树”框中，匹配是如何完成的？在另一篇题为

基于优化匈牙利算法的高效网页变化检测系统[2]

匹配使用匈牙利算法，引用论文中的一句话，题为

一种基于散列和减少相似度计算次数的快速 HTML 网页变化检测方法 [3]

[2] 中的方法使用 O(N ³ ) 匈牙利算法来计算加权二分图上的最大加权匹配，并且运行时间为 O(N ₂ x N ₁ ³ ) ，其中 N ₁和 N ₂是，分别是旧页面和新（更改）页面中的节点数。” 我的问题是，由于子树正在形成为什么要添加权重，以及如何添加它们？

感谢您阅读我的问题/困惑，我真的需要帮助，很快，请任何人帮助我解决这个问题，我将永远感激不尽。

首先我要说我认为我知道应该怎么做，但是我的代码不会以我尝试的任何方式编译。我的假设基于这个空 ptree 技巧的官方示例。在那里你可以找到下一行：

这表明可以（或应该）从 ptree 中获取 subptree。

所以我假设我们可以通过 ptree 以BOOST_FOREACH这样的方式迭代：

但我得到下一个错误：

错误 1 ​​错误 C2440：“正在初始化”：无法从“std::pair<_Ty1,_Ty2>”转换为“const boost::property_tree::ptree &”

或者如果我尝试

我得到：

错误 1 ​​错误 C2039：“empty_ptree”：不是“boost::property_tree”的成员

那么我该怎么办：如何迭代 Boost Ptree 并获得子 Ptree？

更新： 我也试过这样的代码

这会编译，不会抛出任何异常，但不会抛出任何Sub data异常，它只是跳过这个循环。

更新 2：

嗯...我的 xml 中可能出了点问题 - 现在我使用该代码得到了正确的结果。

当我们使用子树合并策略时，git如何找到子树？我在这里只找到一个提及：“它实际上猜测了您要合并的子树。通常，这神奇地证明是正确的，但是如果您的子树包含很多更改（或者最初是空的，或者其他什么），那么它可能会严重失败。” 它是如何猜测的，如果失败了，我该怎么办？自 2009 年 8 月写下该答案以来，有什么变化吗？

在networkX中，我有一棵树作为有向图（）。

如果 a 取树的节点 2。
我怎样才能得到 2 的子树？

编辑

我期待这个子树

我在尝试时遇到问题：（1）在原始树根的左子树中找到最大的信息字段（2）在根的右子树中找到最小的信息字段原始树。

我的代码可以编译，但在执行时出现错误，我不清楚我的 maxleftsubtree() 和 minrightsubtree() 函数中发生了什么。任何建议，将不胜感激。

我当前的代码：

是否有一种简单的方法可以从返回（可能）同一子树的多个后代节点的查询中选择子树（PostgreSQL ltree）的根节点？我已经实现了一个相当冗长的算法来完成这个任务（大约 40 行，缩进和格式化），但是如果我可以利用 ltree 数据实际上是树并且具有易于访问的根节点这一事实，那就太棒了。需要注意的是，单个查询可能会返回多个不同的子树根，因此我不能仅仅对数据进行排序并获取顶部结果。

2012 年 6 月 7 日：我已将查询更新为我的最新版本，这将时间复杂度降低了一半。它使用自反连接（如果您愿意的话）从子树中删除所有在子树中有祖先的节点。

本质上，我的算法如下工作：

（更多细节请看我的要点，这里：https ://gist.github.com/1507368 ）

I'm testing the use of git-subtree to merge a library repo into a bigger project. It seems great in principle. Sometimes when I do a "git subtree pull" I get merge conflicts like this:

That's for a change that was made in the library repo, merging into a file that has not been modified locally. Or another example, where I added a line in the local project repo, but in a file that is part of the subtree being merged:

Why would git report these as merge conflicts, but the region reported as the conflict is empty? Any way to prevent it?

These are easy enough to resolve, but it messes up the git-subtree workflow

最近我在一个项目中广泛使用了 git subtree。一切都很好。现在事实证明，每当我需要为客户提供此类项目时，该项目将被重复使用很多次。您可以想象类似“框架”的东西。

因此，在 Visual Studio 中，我将创建一个“解决方案模板”，用于简单地重复使用骨架部分，仅在需要时进行调整。

但是由于这个骨架是用一堆子树构建的（每个子树都是自己的项目），我需要一种机制来重新创建 git 子树引用。我不希望每个使用骨架（通过解决方案模板或克隆存储库）的开发人员都必须了解重新创建它们的引用。

那么，是否有（最佳实践？）完成此工作流程的方法？提前致谢