DFS 是否可以在没有递归和额外空间的情况下实现
递归和基于向量的迭代过程都可以用于 DFS 树（b 树）遍历。在这两种情况下，我们在递归调用时在堆栈中或在向量中都需要额外的空间。是否存在不需要空间或需要最小空间的技术？
both recursion as well as vector based iterative process can be used for DFS tree(b-tree) traversal. In both the cases, we need extra space either in the stack while recursive calls or in a vector. Does any technique exists which doesn't need space or needs min space?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您正在搜索二叉树，则可以将每条路径表示为位模式。因此，您可以从根点继续向下搜索，并通过调整二进制字中的位来跟踪您的进度。每个级别都需要一点。
例如，
如果我们从A开始搜索，则ABD指定的搜索为00（左-左）；接下来是01，对应左右，或者ABE； 10是AC-无子项； 11是ACF。
请注意，最低有效位指示遍历结束时转向的方向（即选择叶子）；如果以其他方式读取位序列，则此方法将指定广度优先遍历。
由于存储的信息较少，您会不断重新访问相同的节点。
请注意，这相当于对数据进行线性扫描，从而破坏了拥有树的好处。如果您的空间有限而无法负担堆栈，我建议您使用预先分配的向量。如果你保持排序，你可以做像二分搜索这样的事情，这会比这更有效。
If you are searching a binary tree, you can represent each path taken as a pattern of bits. Accordingly, you can keep searching downwards from a root point, and keep track of your progress by twiddling the bits in a binary word. You'll need one bit for each level.
e.g.
If we start searching at A, the search specified by ABD is 00 (left - left); the next is 01, corresponding to left-right, or ABE; 10 is A-C-No child; and 11 is ACF.
Notice that the least significant bit indicates the direction to turn at the end of the traversal (that is, it selects the leaf); if the bit sequence is read the other way, this method would specify a breadth-first traversal.
You keep revisiting the same nodes, as a consequence of storing less information.
Note that this amounts to a linear scan of your data, thus destroying the benefits of having a tree. If you are too space constrained to be able to afford a stack, I suggest that you use a pre-allocated vector. If you keep that sorted, you can do things like binary searches, which will be rather more efficient than this.
遍历树所需的空间最多可以在 log(N) 空间中完成。如果您的节点具有单个分支，则可以使用 O(1) 空间/内存性能来完成。但log(N)性能确实很小。如果您想象有 2^300 个节点（无法容纳在这个宇宙中），则搜索所需的空间约为 300 个，并且可以容纳几 kB 的 RAM。
Needed space for traversing tree can be done at worst in log(N) space. If you have nodes whit single branch it can be done using O(1) space/memory performance. But log(N) performance is really small. If you imagine having 2^300 nodes (can not fit in this universe), you have space requirements for searching that is like 300 and can fit in few kB of RAM.