用 O(1) 辅助空间迭代二叉树 [英] Iterating over a Binary Tree with O(1) Auxiliary Space

问题描述

是否可以在 O(1) 辅助空间(不使用堆栈、队列等)中迭代二叉树，或者这是否已被证明是不可能的?如果可以，怎么做?

Is it possible to iterate over a binary tree in O(1) auxiliary space (w/o using a stack, queue, etc.), or has this been proven impossible? If it is possible, how can it be done?

如果有指向父节点的指针很有趣，我得到的关于这可能的回答很有趣，我不知道这可以完成，但取决于你如何看待它，这可能是 O(n) 辅助空间.此外，在我的实际用例中，没有指向父节点的指针.从现在开始，请在回答时假设这一点.

The responses I've gotten about this being possible if there are pointers to parent nodes are interesting and I didn't know that this could be done, but depending in how you look at it, that can be O(n) auxiliary space. Furthermore, in my practical use case, there are no pointers to parent nodes. From now on, please assume this when answering.

推荐答案

天哪，我必须从 Knuth 那里实际输入它.此解决方案由 Joseph M. Morris [Inf.过程信件9(1979)，197-200].据我所知，它在 O(NlogN) 时间内运行.

Geez, I'll have to actually type it up from Knuth. This solution is by Joseph M. Morris [Inf. Proc. Letters 9 (1979), 197-200]. As far as I can tell, it runs in O(NlogN) time.

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 ;
}

这篇关于用 O(1) 辅助空间迭代二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！