是否可以在 O(1) 辅助空间中迭代二叉树（不使用堆栈、队列等），或者这已被证明是不可能的？如果可能，怎么做？
编辑：如果有指向父节点的指针，我得到的关于这可能的响应很有趣，我不知道这可以做到，但取决于你如何看待它，这可能是 O(n) 辅助空间。此外，在我的实际用例中，没有指向父节点的指针。从现在开始，请在回答时假设这一点。
问问题
14875 次
11 回答
28
天哪，我必须从 Knuth 那里实际输入它。该解决方案由 Joseph M. Morris [ Inf. 过程。信件 9 (1979), 197-200]。据我所知，它在 O(NlogN) 时间内运行。
static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) {
Node parent = root ;
Node right = null ;
Node curr ;
while (parent != null) {
curr = parent.left ;
if (curr != null) {
// search for thread
while (curr != right && curr.right != null)
curr = curr.right ;
if (curr != right) {
// insert thread
assert curr.right == null ;
curr.right = parent ;
preorderVisitor (parent) ;
parent = parent.left ;
continue ;
} else
// remove thread, left subtree of P already traversed
// this restores the node to original state
curr.right = null ;
} else
preorderVisitor (parent) ;
right = parent ;
parent = parent.right ;
}
}
class Node
{
public Node left ;
public Node right ;
}
于 2009-04-26T18:53:09.277 回答
7
如果您在每个孩子中都有指向父母的链接，这是可能的。当你遇到一个孩子时，访问左子树。回来时检查一下你是否是你父母的左孩子。如果是这样，请访问右子树。否则，继续往上走，直到你成为左孩子或直到你碰到树的根。
在此示例中，堆栈的大小保持不变，因此不会消耗额外的内存。当然，正如 Mehrdad 所指出的，到父节点的链接可以被认为是 O(n) 空间，但这更多的是树的属性，而不是算法的属性。
如果您不关心遍历树的顺序，则可以将积分映射分配给根为 1 的节点，根的子节点为 2 和 3，子节点为 4、5、 6、7 等等。然后通过递增计数器并通过其数值访问该节点来循环遍历树的每一行。您可以跟踪可能的最高子元素并在计数器通过时停止循环。从时间上看，这是一个效率极低的算法，但我认为它需要 O(1) 空间。
（我借用了堆编号的想法。如果你有节点 N，你可以在 2N 和 2N+1 找到孩子。你可以从这个数字倒推找到孩子的父母。）
这是该算法在 C 中的一个示例。请注意，除了创建树之外没有 malloc，并且没有递归函数，这意味着堆栈占用恒定空间：
#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
int value;
struct tree *left, *right;
} tree;
tree *maketree(int value, tree *left, tree *right)
{
tree *ret = malloc(sizeof(tree));
ret->value = value;
ret->left = left;
ret->right = right;
return ret;
}
int nextstep(int current, int desired)
{
while (desired > 2*current+1)
desired /= 2;
return desired % 2;
}
tree *seek(tree *root, int desired)
{
int currentid; currentid = 1;
while (currentid != desired)
{
if (nextstep(currentid, desired))
if (root->right)
{
currentid = 2*currentid+1;
root = root->right;
}
else
return NULL;
else
if (root->left)
{
currentid = 2*currentid;
root = root->left;
}
else
return NULL;
}
return root;
}
void traverse(tree *root)
{
int counter; counter = 1; /* main loop counter */
/* next = maximum id of next child; if we pass this, we're done */
int next; next = 1;
tree *current;
while (next >= counter)
{
current = seek(root, counter);
if (current)
{
if (current->left || current->right)
next = 2*counter+1;
/* printing to show we've been here */
printf("%i\n", current->value);
}
counter++;
}
}
int main()
{
tree *root1 =
maketree(1, maketree(2, maketree(3, NULL, NULL),
maketree(4, NULL, NULL)),
maketree(5, maketree(6, NULL, NULL),
maketree(7, NULL, NULL)));
tree *root2 =
maketree(1, maketree(2, maketree(3,
maketree(4, NULL, NULL), NULL), NULL), NULL);
tree *root3 =
maketree(1, NULL, maketree(2, NULL, maketree(3, NULL,
maketree(4, NULL, NULL))));
printf("doing root1:\n");
traverse(root1);
printf("\ndoing root2:\n");
traverse(root2);
printf("\ndoing root3:\n");
traverse(root3);
}
我为代码的质量道歉——这在很大程度上是一个概念证明。此外，该算法的运行时间并不理想，因为它做了很多工作来弥补无法维护任何状态信息的问题。从好的方面来说，这确实符合 O(1) 空间算法的要求，用于以任何顺序访问树的元素，而不需要子链接到父链接或修改树的结构。
于 2009-04-26T15:33:26.447 回答
5
你可以破坏性地做到这一点，在你走的时候断开每一片叶子的链接。这可能适用于某些情况，即当您之后不再需要树时。
通过扩展，您可以在销毁第一个二叉树时构建另一棵二叉树。您将需要一些内存微管理来确保峰值内存永远不会超过原始树的大小加上可能有点恒定。不过，这可能会产生相当多的计算开销。
编辑： 有办法！您可以使用节点本身通过暂时反转它们来照亮备份树的路径。当你访问一个节点时，你将它的left-child指针指向它的父节点，它的right-child指针指向你最后一次右转路径（此时可以在父节点的right-child指针中找到），并将其真正的子节点存储在现在冗余的父级right-child指针或在您的遍历状态中。下一个访问儿童的left-child指针。您需要保留一些指向当前节点及其附近的指针，但不要保留“非本地”。当你回到树上时，你扭转了这个过程。
我希望我能以某种方式说清楚；这只是一个粗略的草图。您必须在某处查找它（我确信这在计算机编程艺术中的某处提到过）。
于 2009-04-26T16:20:16.007 回答
2
为了保留树并且只使用 O(1) 空间，如果......
- 每个节点的大小都是固定的。
- 整个树在内存的一个连续部分（即一个数组）
- 您无需遍历树，只需遍历数组
或者，如果您在处理树时销毁它......：
- @Svante 提出了这个想法，但我想用破坏性的方法稍微扩展一下。
- 如何？可以继续取一棵树最左边的叶子节点(for(;;) node = node->left etc...，然后处理，然后删除。如果树中最左边的节点不是叶子节点，然后处理并删除右节点最左边的叶节点。如果右节点没有子节点，则处理并删除它。
它不会工作的方式......
如果您使用递归，您将隐式使用堆栈。对于某些算法（不适用于此问题），尾递归将允许您使用递归并具有 O(1) 空间，但由于任何特定节点可能有多个子节点，因此在递归调用之后还有工作要做，O(1 ) 空间尾递归是不可能的。
您可以尝试一次解决 1 个级别的问题，但是如果没有辅助（隐式或显式）空间，就无法访问任意级别的节点。例如，您可以递归查找所需的节点，但这会占用隐式堆栈空间。或者您可以将所有节点存储在每个级别的另一个数据结构中，但这也需要额外的空间。
于 2009-04-26T15:32:24.780 回答
1
如果节点具有指向其父节点的指针，则可以实现此目的。当您返回树（使用父指针）时，您还传递了您来自的节点。如果您来自的节点是您现在所在节点的左孩子，那么您将遍历右孩子。否则，您会回到它的父级。
编辑以响应问题中的编辑：如果您想遍历整个树，那么不，这是不可能的。为了爬回树上，你需要知道去哪里。但是，如果您只想遍历树下的单个路径，那么这可以在 O(1) 额外空间中实现。只需使用 while 循环向下迭代树，保持一个指向当前节点的指针。继续沿着树向下，直到找到所需的节点或找到叶节点。
编辑：这是第一个算法的代码（检查 iterate_constant_space() 函数并与标准 iterate() 函数的结果进行比较）：
#include <cstdio>
#include <string>
using namespace std;
/* Implementation of a binary search tree. Nodes are ordered by key, but also
* store some data.
*/
struct BinarySearchTree {
int key; // they key by which nodes are ordered
string data; // the data stored in nodes
BinarySearchTree *parent, *left, *right; // parent, left and right subtrees
/* Initialise the root
*/
BinarySearchTree(int k, string d, BinarySearchTree *p = NULL)
: key(k), data(d), parent(p), left(NULL), right(NULL) {};
/* Insert some data
*/
void insert(int k, string d);
/* Searches for a node with the given key. Returns the corresponding data
* if found, otherwise returns None."""
*/
string search(int k);
void iterate();
void iterate_constant_space();
void visit();
};
void BinarySearchTree::insert(int k, string d) {
if (k <= key) { // Insert into left subtree
if (left == NULL)
// Left subtree doesn't exist yet, create it
left = new BinarySearchTree(k, d, this);
else
// Left subtree exists, insert into it
left->insert(k, d);
} else { // Insert into right subtree, similar to above
if (right == NULL)
right = new BinarySearchTree(k, d, this);
else
right->insert(k, d);
}
}
string BinarySearchTree::search(int k) {
if (k == key) // Key is in this node
return data;
else if (k < key && left) // Key would be in left subtree, which exists
return left->search(k); // Recursive search
else if (k > key && right)
return right->search(k);
return "NULL";
}
void BinarySearchTree::visit() {
printf("Visiting node %d storing data %s\n", key, data.c_str());
}
void BinarySearchTree::iterate() {
visit();
if (left) left->iterate();
if (right) right->iterate();
}
void BinarySearchTree::iterate_constant_space() {
BinarySearchTree *current = this, *from = NULL;
current->visit();
while (current != this || from == NULL) {
while (current->left) {
current = current->left;
current->visit();
}
if (current->right) {
current = current->right;
current->visit();
continue;
}
from = current;
current = current->parent;
if (from == current->left) {
current = current->right;
current->visit();
} else {
while (from != current->left && current != this) {
from = current;
current = current->parent;
}
if (current == this && from == current->left && current->right) {
current = current->right;
current->visit();
}
}
}
}
int main() {
BinarySearchTree tree(5, "five");
tree.insert(7, "seven");
tree.insert(9, "nine");
tree.insert(1, "one");
tree.insert(2, "two");
printf("%s\n", tree.search(3).c_str());
printf("%s\n", tree.search(1).c_str());
printf("%s\n", tree.search(9).c_str());
// Duplicate keys produce unexpected results
tree.insert(7, "second seven");
printf("%s\n", tree.search(7).c_str());
printf("Normal iteration:\n");
tree.iterate();
printf("Constant space iteration:\n");
tree.iterate_constant_space();
}
于 2009-04-26T15:33:50.067 回答
1
使用称为线程树的结构，可以在没有（每个节点两个位）额外存储的情况下拥有从节点指向其祖先的指针。在线程树中，空链接由位状态而不是空指针表示。然后，您可以用指向其他节点的指针替换空链接：左链接指向中序遍历中的后继节点，右链接指向前驱节点。这是一个 Unicode-heavy 图（X 表示用于控制树的头节点）：
╭─┬──────────────────────────────────────╮
╭──────────────────────────▶┏━━━┯━━━┯━━▼┓│ │
│ ╭─╂─ │ X │ ─╂╯ │
│ ▼ ┗━━━┷━━━┷━━━┛ │
│ ┏━━━┯━━━┯━━━┓ │
│ ╭────╂─ │ A │ ─╂──╮ │
│ ▼ ┗━━━┷━━━┷━━━┛ │ │
│ ┏━━━┯━━━┯━━┓ ▲ │ ┏━━━┯━━━┯━━━┓ │
│ ╭─╂─ │ B │ ─╂────┤ ├────────╂─ │ C │ ─╂──────╮ │
│ ▼ ┗━━━┷━━━┷━━━┛ │ ▼ ┗━━━┷━━━┷━━━┛ ▼ │
│┏━━━┯━━┯━━┓ ▲ │ ┏━━━┯━━┯━━━┓ ▲ ┏━━━┯━━┯━━━┓ │
╰╂─ │ D │ ─╂─╯ ╰───╂ │ E │ ─╂╮ │ ╭╂─ │ F │ ─╂╮ │
┗━━━┷━━┷━━┛ ┗━━━┷━━━┷━━━┛▼ │ ▼┗━━━┷━━━┷━━┛▼ │
▲ ┏━━━┯━━━┯━━┓ │ ┏━━━┯━━━┯━━━┓ ▲ ┏━━━┯━━━┯━━━┓│
╰─╂─ │ G │ ╂──┴─╂─ │ H │ ─╂─┴─╂─ │ J │ ─╂╯
┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛
一旦你有了结构，进行中序遍历就非常非常容易了：
Inorder-Successor ( p )
p 指向一个节点。该例程在
中序遍历并返回指向该节点的指针
q ← p .right
If p .rtag = 0 Then
While q .ltag = 0 Do
q ← q .left
End While
End If
返回 q
更多关于线程树的信息可以在计算机编程艺术Ch.2 §3.1 中找到，或者散布在 Internet 上。
于 2009-04-26T16:20:29.313 回答
1
Harry Lewis 和 Larry Denenberg 的“数据结构及其算法”描述了用于二叉树的常量空间遍历的链接反转遍历。为此，您不需要每个节点的父指针。遍历使用树中现有的指针来存储用于回溯的路径。需要 2-3 个额外的节点引用。在每个节点上加上一点，以便在我们向下移动时跟踪遍历方向（向上或向下）。在我对书中这些算法的实现中，分析表明这种遍历的内存/处理器时间要少得多。java中的一个实现是here。
于 2013-11-03T07:37:15.363 回答
0
http://en.wikipedia.org/wiki/XOR_linked_list
将您的父节点编码为叶指针
于 2012-04-24T21:49:25.760 回答
0
对的，这是可能的。这是我的迭代示例，它具有 O(n) 时间复杂度和 O(1) 空间复杂度。
using System;
public class Program
{
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static void Main()
{
TreeNode left = new TreeNode(1);
TreeNode right = new TreeNode(3);
TreeNode root = new TreeNode(2, left, right);
TreeNode previous = null;
TreeNode current = root;
TreeNode newCurrent = null;
while(current != null) {
if(current.left == null) {
if(current.right == null) {
if(previous == null) {
Console.WriteLine(current.val);
break;
}
Console.WriteLine(current.val);
current = previous;
previous = previous.left;
current.left = null;
} else {
newCurrent = current.right;
current.right = null;
current.left = previous;
previous = current;
current = newCurrent;
}
} else {
newCurrent = current.left;
current.left = previous;
previous = current;
current = newCurrent;
}
}
}
}
每次看到 时Console.WriteLine(current.val);，您都应该将代码用于值处理。
于 2021-03-11T17:55:52.843 回答
-2
我认为你不可能做到这一点，因为你应该以某种方式找到你在路径中离开的节点并确定你总是需要 O(height) 空间。
于 2009-04-26T15:41:24.073 回答
-3
是否可以在 O(1) 辅助空间中迭代二叉树。
struct node { node * father, * right, * left; int value; };
这种结构将使您能够在二叉树的任何方向上移动 1 步。
但仍在迭代中，您需要保持路径！
于 2012-04-24T21:24:00.937 回答