6

给定一棵具有整数、左右指针的二叉树，如何在 O(n) 时间和 O(1) 额外内存（无堆栈/队列/递归）内遍历树？

这个人给出了一个不是 O(n) 总时间的解决方案，它将当前路径编码为一个整数（因此适用于深度有限的树）。

我正在寻找经典的解决方案

（剧透）

对子节点中每个节点的父节点进行编码。

4

5 回答 5

6

任何好的算法书都会有这个算法，例如看 Knuth（TAOCP I.2.3.1 遍历二叉树，练习 21）。但是，由于此算法会就地修改树，因此在多线程环境中必须格外小心。

您也可以使用线程树（参见 Knuth）。

于 2009-04-05T09:47:03.440 回答
3

主要思想类似于列表反转算法，基于指针（在人类目前已知的所有语言中）0 模式这一事实，有一个超级丑陋的技巧（从理论的角度来看，可能是作弊） 4 作为整数。

这个想法是，您可以将路径上的指针翻转到树下以指向上方。问题是——这就是你从列表反转算法转移的地方——当你回溯时，你需要知道是左指向上还是右指向上；此时我们使用 hack。

伪代码如下：

current = root->left
next = current
while (current != null) {
  next = current->left
  current->left = static_cast<int>(prev) + 1 // ugly hack.
  current = next
}
status = done
while (current != root or status != done) {
  if (status = done) {
     if (static_cast<u32>(current->left) %4 = 1) {
         next = static_cast<u32>(current->left) -1
         current->left = prev
         status = middle
     }
     else {
         next = current->right
         current->right = prev
         status = done
     }
     prev = current
     current = next
  }
  else if (status == left) {
     if (current->left) {
       prev = current->left
       current->left = static_cast<u32>(next) +1
       next = current
     }
     else
       status = middle
  }
  else if (status == right) {
     if (current->right) {
        prev = current->right;
        current ->right = next;
        next = current
     }
     else
       status = done
  }
  else {// status == middle
     work_on_node(current)
     status = right
  }
}
于 2009-04-07T06:05:51.880 回答
1

那家伙的算法很有趣，但需要指出的是，它确实需要 O(log n) 额外的空间来遍历具有 n 个节点的二叉树。空间需求必须以位而不是字节来衡量——通常在使用 Big Oh 表示法时它们会合并为同一事物，但是像这样的案例指出了为什么区分很重要。

要了解这一点，请询问如何使用单个整数存储（在 32 位平台上）遍历具有超过 2^32-1 个节点的树。

于 2009-04-06T03:17:28.423 回答
0

使用 O(1) 存储来记住“最后访问的节点”指针。您可以将其初始化为 0 或某个未知值。

要遍历树，请从根节点开始。查看节点的两个子节点。如果您的“最后访问节点”等于 RIGHT 节点，则进入父节点。如果“最后访问”等于 LEFT 节点，则跳到右节点。其他步骤到左侧节点。

重复直到你走完整棵树。唯一真正的聪明之处是使用一个变量来记住你来自哪里，以便决定下一步去哪里。这使得遍历具有确定性。

你最终会采取 O(n) 步骤。您将访问每个中间节点 3 次，每个叶子访问一次，所以您仍然是 O(N)。存储是 O(1)。

于 2009-04-06T12:14:34.420 回答
0

这是另一个解决方案

http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

但我想知道是否有一种方法可以在像 Java 这样没有真正意义上的指针的语言中做到这一点。

于 2010-09-12T15:41:15.480 回答