问题标签 [tree-traversal]

如何在n不使用递归的情况下遍历 -ary 树？

递归方式：

我在 C# 中编写了一个递归目录遍历方法（托管自 asp.net 页面）。代码按我的预期工作（我枚举目标机器上的共享列表，然后通过共享递归并将每个文件/目录添加到 TreeView）。不幸的是，这会消耗大量内存并且需要很长时间才能运行，打开 aspx 页面会导致 Webdev.Webserver 内存使用量飙升至 800 兆字节，而查看该页面的 Chrome 实例消耗了高达 1.5GB 的内存！（针对托管在本地工作站上的 SMB 共享运行测试代码）我什至无法在没有 chrome 挂起的情况下查看页面源代码。

取消注释 //break; 语句只处理第一个目录共享，这消耗的内存要少得多。FileSelectList 是一个 Asp:TreeView。

由于创建了大量的 TreeNode 对象，这似乎会导致极端的资源使用。我应该创建自己的节点类型以尽可能减少内存使用，还是有另一种技术可以使它可用？

我正在考虑重构一个开源项目Afterthought，使其使用起来更直观。基本思想是，在 Afterthought 中创建修改的开发人员将修改特定的 .NET 类型，并有机会修改类型本身以及属性、方法、事件、构造函数等列表（树）。我在内部使用的 API微软 CCI 元数据在他们的 API 中广泛使用了访问者模式，所以我在 Afterthought 中采用了类似的方法，如下所示：

但是，我发现访问者模式实际上最终会将解决目标问题的代码（例如检测类库）重新分配到一系列不同的方法中，这些方法专注于树的各个方面。对于创建 API 的开发人员来说，这很容易实现，但消费者必须以某种不自然的方式将他们的代码分散开来。所以我提出了一个问题，与仅将树公开为列表并利用 LINQ 样式的方法相比，vistor 模式有什么好处？

这是我正在考虑的替代语法：

因此，在这种情况下，修正案的作者可以通过与公开 fluent/LINQ API 而不是覆盖方法的列表交互，将所有代码写在一个地方（或他们选择的地方）。显然这种方法的性能稍差（更多迭代等），但除此之外，还有什么缺点？

我很难遍历树，所以像瘟疫一样避免它......通常。

我有一个类（这里稍微简化版本，但功能相同），例如：

我有一堆Branch实例的字典，每个实例的标题作为键：

现在，我知道有一些复杂的算法可以提高遍历效率（例如 MPTT 等），特别是用于效率最重要的数据库驱动项目。我根本不使用数据库，只使用简单的内存对象。

鉴于titlea Branch，我需要从 获取list该分支的所有后代（孩子，孩子的孩子，等等）的a tree，所以：

1. 您是否仍然建议使用复杂的（对于我的无算法大脑:)算法，例如 MPTT 以提高效率，或者是否有一种简单的方法可以在单个函数中实现这一点？
2. 如果是这样，你会推荐哪一个，知道我没有使用数据库？
3. 你能提供一个例子，还是这比我想象的要大得多？

注意：这不是家庭作业。我不在学校。我在算法方面真的很糟糕。我已经将 Django MPTT 用于需要数据库存储树的项目......但仍然不太了解它。

我有一系列包含产品信息的对象，我需要使用这些对象来过滤可用的产品选项。（即客户选择值选项 id 为 25 的单选按钮，我需要根据 id 25 可用的内容过滤其他两个选项，然后从配置（25 / 1 / 13）中获取该三部分组合的值并找到该组合在兄弟姐妹中返回 sku 值 (25 / 1/ 13 = 1761)。

我已经成功获得键和值但不匹配。我是 javascript 的完全 n00b（我的大部分经验只是用 jQuery 制作动画）所以我不确定到目前为止我是否写过任何有价值的东西。

这是我从编码的 JSON 中得到的信息（修剪后的 b/c 数据量很大，因此格式可能不准确）。我无法控制 JSON 的格式和结构。

这是产品形式的通用结构：

有任何想法吗？谢谢！！

编辑

这是两者的完整对象：

我得到以下代码：

基本上我正在对“a.issueDrawer”执行一个动作，它应该为“tr.issueDrawer”设置动画。从“a.issueDrawer”我目前正在做$(this).parent().parent().next()，但必须有一种更简洁的方法来遍历并找到第一个“tr.issueDrawer”。

想法？

寻找一个就地 O(N) 算法，该算法打印节点对（在遍历树时），如下所示，对于给定的平衡二叉树：

输出：bc、de、ef、fg

其中“a”是根节点，“b”是左子节点，“c”是右子节点，等等。请注意输出中的“ef”对。

基于以下评论的附加信息：

1. “节点对”是每个级别的每个相邻对
2. 除了“左”和“右”之外，每个节点都可以有“父”指针/引用
3. 如果我们要放松 O(N) 并就地，是否有更简单的解决方案（递归和迭代）？

我有一个 HTML 列表（<ul>,<li>等），其中包含不同深度的多个项目。我正在尝试编写一些代码来一次遍历这个列表一个元素。因此，“下一个”按钮将返回下一个<li>元素的 ID，它可能是当前元素的直接兄弟元素，也可能在子<ul>元素中，也可能在父<ul>元素中。同样，“上一个”按钮也会做同样的事情，但相反。

这是一些示例html：

我已经用 jquery 玩了几个小时，这就是我所得到的：

以上将返回下一个节点，如果有则返回子节点，如果没有更多兄弟节点或子节点，则返回父节点，但只有一层深。HTML 列表可以是无限深度的，所以可能需要某种递归？这是我的技能所能带给我的。我什至还没有开始考虑“上一个”链接，以相同的方式但以相反的顺序处理此列表。

我（几周前）在 devshed 上问过同样的问题，但没有得到任何答复。

谢谢大家的答案。

忍者，我已经成功地实现了你的。我现在可以很好地上下导航我的嵌套列表。

另一个问题，如果你愿意的话：我需要能够在树中的某个点开始“位置”。用户可以通过散列（例如#post9）在树中选择一个节点——他们可以单击列表中任意位置的节点来选择它，或者他们可以将包含该节点自己的散列的url 加入书签。

所以我的进一步问题是：如何使用 URL 中的哈希在树中定位节点并获取它的位置？URL 中的哈希与 li 节点的 id 相关。

我需要快速遍历一棵树，并且我想并行执行。我宁愿使用并行扩展而不是手动启动一堆线程。

我当前的代码如下所示：

我真的希望 Parallel.ForEach 有一个 Parallel.While 模拟。我看到了 Stephen Toub 的关于使用 Parallel.ForEach 实现 Parallel While的文章。如果正确阅读，这仍然不起作用，因为我正在改变我试图迭代的队列。

我是否需要使用任务工厂和递归（这有风险吗？）？还是有一些我忽略的简单解决方案？

编辑：@svick

这棵树有超过 250,000 个节点。现在的最大深度是 14 个节点，包括根。

离根节点大约有 500 个节点，之后的余额具有相当随机的分布。我很快就会得到一些关于分布的更好的统计数据。

@谜：

是的，树正在被许多用户同时修改，但我通常会为树或子树设置一个共享读锁，或者允许脏读。

对 node.Children 的调用可以被认为是原子的。

DoSomething 实际上是几个委托之一，对于一些昂贵的操作，我可能会收集节点的快照列表并在遍历之外处理它们。

我意识到我可能应该查看一般情况（遍历子树而不是整个树。）为此，我在树的每个节点上运行遍历并查看总时间。

我为每个遍历算法使用了 Parallel.ForEach(nodes, Traverse)，其中节点包含所有 ~250k 节点。这模拟（某种程度）许多用户同时请求许多不同的节点。

00256ms 广度优先顺序

00323ms 广度优先顺序与工作（我增加了一个静态计数器作为“工作”）

01495ms 柯克斯第一个答案

01143ms Svicks 第二个答案

00000ms 递归单线程在 60 秒后未完成

00000ms Enigmativity 的答案在 60 秒后没有完成

@Enigma，我认为我可能以某种方式弄乱了您的算法，因为它似乎应该更快。

结果至少可以说让我感到惊讶。我不得不在广度优先顺序上添加一些工作，只是为了让自己相信编译器并没有神奇地优化遍历。

对于头部的单次遍历，并行化第一级只有最好的性能。但几乎没有，随着我在第二级添加更多节点（2000 而不是 500），这个数字有所改善。

我正在阅读《计算机程序的结构和解释》一书，其中讲述了递归过程和递归过程之间的区别，以及迭代过程和迭代过程之间的区别。因此，递归过程仍然可以生成迭代过程。

我的问题是：给定一个生成递归过程的过程，您是否总是可以编写另一个实现相同结果但生成迭代过程的过程？

我试图解决的具体问题是编写一个按顺序遍历二叉搜索树但生成迭代过程的过程。我知道如何使用堆栈来获得解决此问题的迭代过程。但是，这仍然会产生一个递归过程（如果我在这里错了，请纠正我）。

谢谢，
阿比纳夫。