用O(1)辅助空间迭代二叉树

Question

是否有可能在O(1)辅助空间中迭代二叉树(没有使用堆栈,队列等),或者这被证明是不可能的？如果有可能,怎么办呢？

编辑:如果有关于父节点的指针很有趣并且我不知道这可以做到,那么我得到的关于这可能的响应是可能的,但是根据你如何看待它,可以是O(n)辅助空间.此外,在我的实际用例中,没有指向父节点的指针.从现在开始,请在回答时假设这一点.

Answer 1

Geez,我必须从Knuth中输入它.该解决方案由Joseph M. Morris [ Inf.PROC.信件 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 ;
}

Answer 2

如果您有每个孩子的父母的链接,则可能.遇到孩子时,请访问左侧子树.回来时检查你是否是你父母的左孩子.如果是这样,请访问正确的子树.否则,继续往上走,直到你是左孩子或直到你击中树的根.

在此示例中,堆栈的大小保持不变,因此不会消耗额外的内存.当然,正如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)空间算法的要求,用于以任何顺序访问树的元素,而不需要子到父链接或修改树的结构.

Answer 3

你可以破坏性地做到这一点，一边走一边解开每一片叶子。这可能适用于某些情况，即当您之后不再需要树时。

通过扩展，您可以在销毁第一个二叉树时构建另一个二叉树。您将需要一些内存微管理以确保峰值内存永远不会超过原始树的大小加上一些常数。不过，这可能会有相当多的计算开销。

编辑： 有办法！您可以使用节点本身通过暂时反转它们来照亮返回树的路径。当你访问一个节点时，你将它的left-child指针指向它的父节点，它的right-child指针指向你最后一次在你的路径上右转（此时可以在父节点的right-child指针中找到），并将其真正的子节点存储在现在冗余的父right-child指针或在您的遍历状态中。下一个访问了孩子的left-child指针。您需要保留一些指向当前节点及其附近的指针，但没有“非本地”。当你回到树上时，你逆转了这个过程。

我希望我能以某种方式清楚地说明这一点；这只是一个粗略的草图。您必须在某处查找它（我确信《计算机编程艺术》中的某处提到了这一点）。

Answer 4

为了保留树并且只使用 O(1) 空间，如果......

• 每个节点都有固定的大小。
• 整个树位于内存的连续部分（即数组）
• 您不需要迭代树，只需迭代数组

或者，如果您在处理树时破坏了它......：

• @Svante 提出了这个想法，但我想使用破坏性的方法来扩展一点。
• 如何？可以继续取一棵树中最左边的叶子节点（for(;;) node = node->left etc... ，然后处理它，然后删除它。如果树中最左边的节点不是叶子节点，然后处理并删除右节点的最左叶节点。如果右节点没有子节点，则处理并删除它。

有哪些方法是行不通的...

如果您使用递归，您将隐式使用堆栈。对于某些算法（不适用于此问题）尾递归将允许您使用递归并具有 O(1) 空间，但由于任何特定节点可能有多个子节点，因此在递归调用之后还有工作要做，O(1 ) 空间尾递归是不可能的。

您可以尝试一次解决 1 个级别的问题，但是如果没有辅助（隐式或显式）空间，则无法访问任意级别的节点。例如，您可以递归查找所需的节点，但这会占用隐式堆栈空间。或者，您可以将所有节点存储在每个级别的另一个数据结构中，但这也需要额外的空间。