问题标签 [tree-traversal]

对于我们在数据结构中给出的任务，我们必须创建一个测试类来确定我们得到的代码是否正确地遍历了我们测试类中的二叉树。

这些是提供给我们的 BinaryTreeNode 类的 3 个构造函数：

我很快在我的测试类中进行了以下操作，以创建指定的树之一：

但是，我的朋友建议我这样做：

然而，他很难解释为什么这种方式更好。有人可以解释为什么这更有效吗？如果示例中需要更多代码，请询问。

首先，这个问题不是这个问题的重复，而是建立在它之上。

以那个问题中的树为例，

你会如何修改你的程序来打印它，

而不是一般的

我基本上是在寻找最有效的方法的直觉——我有一种方法涉及将结果附加到列表中，然后循环遍历它。一种更有效的方法可能是在弹出的每个级别中存储最后一个元素，然后打印出一个新行。

想法？

当递归遍历目录结构时，如果文件多于目录，使用什么算法最有效？我注意到当使用深度优先遍历时，当给定目录中有很多文件时，它似乎需要更长的时间。在这种情况下，广度优先遍历是否更有效？我目前无法描述这两种算法，因此非常欢迎您的见解。

编辑：响应 alphazero 的评论，我在 Linux 机器上使用 PHP。

我正在尝试遍历 C 中的二叉树。我的树包含一个 AST 节点（编译器的抽象语法树节点）。ASTnode保留nodetype指定给定节点的类型（即INT OP或CHAR和TYPE我们不需要关心其他类型），其他成员是左右指针，最后我们存储。

这是遍历的代码：

此外，我们不能为 CONSTANT 节点分配左值或右值，因为在 AST 中，常数值不包含任何额外值。

更新：

问题出在我的主要电话中：

如果我们删除 node5（由 !! 标记），则代码运行良好，否则会出现分段错误。

作用于 的函数makenode：

我正在寻找在层次结构/树结构上进行交互设计的灵感。（具有多个子产品的产品，适用于选择子产品的规则）。

我想要一棵树，其中子节点与其父节点之间存在可见的连接。而且我还想可视化适用于选择它们的规则。

典型规则：

• 强制：仅选择一种子产品之一
• 可选：从多个子产品中选择 0 个或多个
• 互斥：只选择几个子产品之一

我希望你能明白。

我正在寻找这方面的任何灵感。欢迎任何建议，示例，提示

我有一个类似的数组：

但是我需要一个函数来递归地将每个项目放入相关父数组内的“子”数组中。所以它看起来更像这样：

我希望这是有道理的！

我能够在不使用递归的情况下理解前序遍历，但是我很难进行中序遍历。我只是似乎不明白，也许是因为我不了解递归的内部工作。

这是我迄今为止尝试过的：

内部的while循环感觉不对。此外，一些元素被打印两次；可能我可以通过检查该节点之前是否已打印来解决此问题，但这需要另一个变量，这再次感觉不对。我哪里错了？

我没有尝试过后序遍历，但我想它是相似的，我也会在那里面临同样的概念障碍。

谢谢你的时间！

PS：Lifo和的定义Node：

我需要在二叉树的单个级别上打印（访问）节点。
我不明白如何做到这一点，但我又不是很擅长一般的算法。
我知道在广度优先遍历中你使用一个队列，你首先将根节点放入队列然后你出队它访问它并将它的孩子排队然后你将第一个入队的孩子出队访问它并将它的孩子排队等等on...
据我了解，除非您在创建二叉树时为每个节点分配其级别，然后在进行广度优先遍历时检查该级别，否则无法准确知道一个级别何时结束而另一个级别何时开始.

像这样的东西（代码在 PHP 中，但这不是 PHP 相关问题，而是与一般算法相关的问题 - 这是添加节点到二叉树的函数的一部分，在添加每个节点时存储节点中的级别):

所以我的问题是：

这是在二叉树的单个级别上打印节点的唯一方法吗？
还有其他方法吗？
在创建树时是否有另一种不存储关卡的方法？

我已经实现了一个迭代算法，其中每次迭代都涉及一个前序树遍历（有时称为向下累积），然后是一个后序树遍历（向上累积）。对每个节点的每次访问都涉及计算和存储要用于下一次访问的信息（在后续的后序遍历或后续迭代中）。

在前序遍历过程中，每个节点都可以独立处理，只要它与根之间的所有节点都已经被处理过。处理后，每个节点需要将一个元组（特别是两个浮点数）传递给它的每个子节点。在后序遍历中，每个节点都可以独立处理，只要它的所有子树（如果有的话）都已经被处理过。处理后，每个节点需要将一个浮点数传递给它的父节点。

树的结构是静态的，在算法过程中是不变的。但是，在向下遍历的过程中，如果被传递的两个浮点数都为零，则不需要处理该节点下的整个子树，可以开始对该节点的向上遍历。（必须保留子树，因为在后续迭代中传递的浮点数可能在该节点处变为非零并且遍历将恢复）。

每个节点的计算强度在树上是相同的。每个节点的计算是微不足道的：只需对长度等于节点上的子节点数的数字列表进行一些求和和乘/除。

正在处理的树是不平衡的：一个典型的节点会有 2 个叶子加上 0-6 个额外的子节点。因此，简单地将树划分为一组相对平衡的子树是不明显的（对我来说）。此外，这些树旨在消耗所有可用的 RAM：我可以处理的树越大越好。

我的串行实现仅在我的小测试树上就达到了每秒 1000 次迭代的量级；对于“真正的”树，我预计它可能会减慢一个数量级（或更多？）。鉴于该算法需要至少 1 亿次迭代（可能高达 10 亿次）才能达到可接受的结果，我想并行化该算法以利用多个内核。我对并行编程的经验为零。

鉴于我的算法的性质，推荐的并行化模式是什么？

我正在使用这个库来保存有关树结构的信息：

http://www.datasoftsolutions.net/tree_container_library/overview.php

这是我的 C++ 代码的简化版本：

树长这样

我正在尝试创建一个函数，给定 Node(6) 将遍历所有通向根节点的节点，即6,5,3,0。这是我在 C++ 中的第一个项目，我无法理解指针。可能是几行 C++，但我试图这样做几个小时但没有成功。任何帮助将不胜感激。

像这样的东西有效，但它必须与许多级别一起工作，而不仅仅是 4：