问题标签 [tree-traversal]

我正在尝试在 Excel 中为我的时间表创建一个树遍历。我现在有 2 个列表，每个 1006 个单元格长。一是前人，二是后人。我正在尝试使用一组函数来显示多个结果。例如，如果我输入 3，我希望列出任务 3 的所有继任者。到目前为止，我想出的代码是：

但是，当我输入前任时，它不会显示正确的后继。

预先感谢任何可以帮助我的人

给定这个二叉树（实际上，二叉树可以是随机的和动态的，这只是一个例子......）：

请参阅二叉树图像的链接：二叉树示例

这是给定的事实：

1. 所有节点都连接到它们的父亲，以便我们可以从下到上（当然也从上到下）遍历。
2. 所有节点都保存关于它们左右部分有多少后代的信息。

问题是这样的：我需要找到一种方法来计算级别 2 中的节点总数（实际上，在任何级别，但现在，让我们专注于级别 2）。显然，如果我们事先知道二叉树的结构，答案是 3，但假设我们没有这个图像，只有给定的事实。

这里的另一个问题是我们将从第 2 级（我们的目标级别）中的节点而不是根节点开始。在这个例子中，我选择了 NODE F。

我知道使用广度优先顺序遍历是直接的解决方案，但我发现它太耗时了，因为每次我读取一个节点时，我都会从数据库中查询它。

我正在寻找更实用的方法。但是，如果由于给定数据不足而“不可能”解决这个问题，请告诉我应该提供哪些其他数据才能解决这个问题。我会评估它是否可行。

顺便说一句，我正在创建一个网站，并使用 PHP 和 MySQL。但我只想要解决方案的概念或解释，更像是算法而不是编程片段或代码......

我希望有人能回答我...非常感谢！

好的。我有一个二叉树，这就是我想要做的：

对于原始树中的每个节点：如果它不是叶子，则将其替换为叶子节点。对使用删除的分支更新的原始树进行计算。将节点恢复到原来的样子（所以现在树与开始时相同）。

问题是这样的：我正在使用堆栈遍历树。如果我将 stack.pop() 节点更改为叶子，这不会删除原始树中的任何分支。这与您为什么可以这样做的原因相同：

x 仍然等于 1。对此有一个技术术语，但我忘记了。

那么如何编辑原始树中的节点并仍然遍历它呢？

这基本上就是我现在正在做的遍历树：

我使用图形数据库 Neo4J 对有向树结构进行了建模。所以我有这样的东西：http: //ouwarovite.net/YAPC/220px-Binary_tree.svg.png（非强制性二进制）

我的数据库的用户可以随意添加已有节点的子节点，所以树的高度和单个节点的度数是未知的。

现在，我想像这样查询我的树：从节点 x 开始，给我所有叶子是叶子 x 的后代。

这种查询是否可以使用 Gremlin 或 Cypher 执行，如果可以，如何实现最大性能？（我还没有找到对“通用”树执行查询的可能性，因为您总是必须指定最大深度）

我知道，使用 REST / JSON 框架和 JAVA API 是可能的，如下所示：

（我的叶子有属性'leave'，我的边缘没有类型->所以_default）

有没有更简单/更好的方法来做到这一点，也许性能更好？

我使用 Neo4J 图形数据库对树结构进行了建模。所有节点都代表一个具有特征名称的类别。所以我必须经常从根到特定的节点/类别遍历我的树。哪个节点取决于作为输入的列表。此列表包含表示从根节点到目标节点的类别名称的字符串。

我想知道，将这些名称存储为边的类型而不是特定节点中的名称属性是否有效。我认为当我这样做时，Neo4J 不必每次在树中更深入地查找每个子节点的合适名称属性。相反，Neo4J 可以在包含传出边的地图中查找名称。

你怎么看？

我需要深度优先和广度优先遍历顺序的任意树的树遍历算法。棘手的部分是我需要能够从任意节点开始并继续直到遍历另一个特定节点。

现在，我可以使用任何普通算法并忽略遍历的节点，直到我到达开始节点并继续直到结束节点（我目前正在这样做），但这既丑陋又低效。

请有任何建议。

更新：我的每个节点都有一个与之关联的 id。在某些情况下，我有开始和结束节点引用作为开始。在其他情况下，我有两个 ID，我通过检查它们的 ID 来检查给定节点是开始节点还是结束节点。我使用深度优先遍历来查找起始节点。开始节点和结束节点都可以位于层次结构中的任何位置。我希望有人可以为我已经参考起始节点和结束节点的情况提出一个想法。BTW，树中的节点实际上是按照排序顺序排序的，一个节点的每个子节点从0开始，并且有一个根节点

Actually what I want to know is not how to implement the in-order traversal algorithm for a BST but to implement it only using insertion, deletion and pre-order traversal algorithms for a BST.
You can assume that you are given the implementations for standard BST algorithms for insertion, deletion and pre-order traversal.

我刚遇到这个问题，想知道我是否能想出一个正确的解决方案。问题涉及交换二叉树的两个节点，不仅按值，而且按节点。所以这意味着我们也必须改变右值和左值。

因此，可以说我们有一个类似于上图的二叉树。我最初的想法是对节点进行中序遍历，以便我可以展平树，然后交换元素，然后从交换的列表中重建树。所以从字面上看，解决方案是这样的

对于上面提到的树，中序遍历会生成一个这样的列表，

1,3,4,6,7,8,10,13,14。

现在我交换 8 和 13。

=> 1,3,4,6,7,13,10,8,14

但是这里的问题是，由于我现在在尝试重建时已将树展平，所以我无法这样做，因为我不知道各个节点的位置，例如特定节点是左子节点还是它是一个根。因此，从字面上看，树不能像最初使用交换节点时那样重新生成。

现在的问题是我是否可以修改我的遍历算法来保存每个节点的位置信息，以便当我交换元素并重建时，我想出与交换所需节点相同的二叉树？我们可以在中序遍历期间存储各个节点的状态/位置吗？

PS。我认识到进行后排序会使我的列表包含要交换的第一个和最后一个节点，但是需要交换的两个节点不一定位于根和最右边的元素，它可以是任意两个。

我不确定我想要执行的确切遍历类型的名称，但基本上我想从当前元素以相反的顺序逐个元素地读取文档元素。

该iterdescendants()方法似乎没有做任何事情，并且该iterancestors()方法没有进入子元素，它只是逐步退出，如果您知道我的意思的话。

我需要遍历二叉树，跳过满足条件的任何节点的子节点。

这实现了树引导的聚类方法；当子树的叶子共同满足条件时，它们被认为是一个簇。

似乎开始的地方是预购遍历，但我不确定如何修改算法以跳过当前节点的所有子节点。

更新

除了以下两个（正确）答案之外，还可以使用以下 Java 库：

• MyArch TreeIter - 通用（带有适配器类）树遍历，带有子跳过和动态最大遍历深度
• Phylosoft ForestergetAllExternalDescendants - 带有Newick-to-XML 转换器的树实现