问题标签 [tree-traversal]

我有一个自定义对象，其中包含一个数组（称为“子项”），其中将存储相同类型的对象，从而创建一棵树。
假设它看起来像这样：

现在，我想向该对象添加一个“forAll”方法，该方法将以深度优先的方式在该树的所有元素上执行作为参数提供的另一个函数。最好的方法是什么？

树遍历的时间复杂度是多少，我敢肯定它一定很明显，但我可怜的大脑现在无法计算出来。

好吧，就像标题一样，由于这些事情，我遇到了问题。问题是由于 X 行而发生的，它位于SitePoint 的 Tree Traversalwhile ($right[count($right)-1]<$row['rgt']) {的函数 display_tree 中。

该功能运行良好，但我不知道为什么它突然开始抛出这个致命错误。

我尝试使用error_reporting(-1);以了解可能导致错误的原因，新的错误日志显示我多次收到 PHP 通知，就像在未完成的循环中一样，直到我收到内存不足错误。

奇怪的是，直到两天前，这一直运行良好，因为当我拔出头发来破译导致问题的原因时。

有什么方法可以准确了解导致问题的原因？或者可能是其他一些有用的提示？

这是它的条件内的while循环：

多谢你们。

对于我自己的练习，我正在编写一个 XML 解析器。为了填充树，我使用法线std::stack并将当前节点设置为最后一个顶部节点的子节点（应该是深度优先？）。所以我现在对删除节点做同样的事情，我想知道是否有更快的方法。
当前删除代码：

工作得很好，但看起来有点慢。那么有没有更快/更好/更常见的方法来做到这一点？

鉴于此依赖关系图：从下到上遍历它的“好”方法是什么？

我对每个“周期”的预期结果是：

头脑风暴

“深度优先搜索”不起作用的原因：

算法

我真的不想重新发明轮子：那么是否已经有一种算法可以解决这个问题，或者有没有人有一个“聪明”的方法？

我怎样才能打开这个树形结构

....进入这个“反向树”结构，它基本上包含从所有叶节点到 1（根）的路径：

结果甚至不必构造为树，以正确顺序排列的四个平面数组也可以。

看起来深度优先搜索可能是一种相关算法，但我无法理解伪代码（incidentEdges() 返回什么？），所以我很困惑。

如果有人可以提供一种 Ruby 方法（或非常容易理解的伪代码）将原始嵌套数组转换为结果数组，我将不胜感激。

这不是家庭作业，而是因为我学习时间太长了......我需要这个来为问题跟踪器中的给定问题以正确的顺序打印依赖关系树。

我正在做这个作业，我需要按前序、后序和中序打印我的二叉搜索树。但是，似乎只有我的中序方法有效。我使用以下测试用例来检查我的工作。

你能看看我下面的代码，看看我做错了什么。任何帮助/方向将不胜感激。你不必为我解决它，只要让我知道我做错了什么。谢谢。

这不是作业，这是一道面试题。

这里的问题是算法应该是常数空间。我对如何在没有堆栈的情况下执行此操作一无所知，我会发布我使用堆栈编写的内容，但无论如何它都不相关。

这是我尝试过的：我尝试进行预订遍历，然后到达了最左边的节点，但我被困在那里。我不知道如何在没有堆栈/父指针的情况下“递归”备份。

任何帮助，将不胜感激。

（我将其标记为 Java，因为这是我很喜欢使用的，但显然它与语言无关。）

有人可以在不使用堆栈或递归的情况下帮助我理解以下莫里斯中序树遍历算法吗？我试图了解它是如何工作的，但它只是逃避了我。

我了解树的修改方式是,current node是in并使用此属性进行中序遍历。但除此之外，我迷路了。right childmax noderight subtree

编辑：找到这个随附的 c++ 代码。我很难理解树在修改后是如何恢复的。神奇之处在于else子句，一旦右叶被修改，就会被击中。详情见代码：

我不能用 prev 更改 css，我的错误在哪里？小提琴链接

坦克寻找！

CSS：

html:

查询：