6

我正在阅读一本名为“算法简介”的书。我想你们很多人都知道。我刚刚碰到一个似乎相当困难的问题：

编写一个 O(n) 时间的非递归过程，给定一个 n 节点二叉树，打印出每个节点的键。在树本身之外使用不超过恒定的额外空间，并且在过程期间不要修改树，即使是临时的。

我看到还有这样一个问题：How to traverse a binary tree in O(n) time without extra memory但主要区别是我不能修改树。我正在考虑使用一些访问过的标志，但我还没有提炼出正确的解决方案。这可能是我看不到的显而易见的事情。你将如何设计一种算法来解决这个问题？甚至一些指向答案的指针也将不胜感激。

4

3 回答 3

9

如果树在两个方向上链接，您可以这样做：

assert root.parent is null

now, old = root, null
while now != null:
    print now.label
    if leaf(now):
        now, old = now.parent, now
    else:
        if old == now.right:
            now, old = now.parent, now
        if old == now.left:
            now, old = now.right, now            
        if old == now.parent:
            now, old = now.left, now

这以根、左、右顺序打印，但您可以得到任何您喜欢的顺序。

如果树只在一个方向上链接，我认为你不能做到这一点。你可以看看森林砍伐。

于 2012-06-14T17:38:08.043 回答
0

有完整的代码（在 Ruby 中）。

例如，我复制了与“算法简介”一书中相同的“n 节点二叉树” 。

class Node
  attr_accessor :key, :parent, :left, :right

  def initialize(key, parent)
    @key = key
    @parent = parent
  end
end

class Tree
  def initialize(root)
    @root = root
  end

  def print_with_constant_space
    current, old = @root, nil
    while current do
      # Going UP
      if old && old.parent == current
        # Go right if exists
        # otherwise continue up
        next_node = (current.right || current.parent)
        current, old = next_node, current

      # Going DOWN
      else
        puts current.key

        # Go left if exists
        # otherwise go right if exists
        # otherwise go up
        next_node = (current.left || current.right || current.parent)
        current, old = next_node, current
      end
    end
  end
end

root         = Node.new(0, nil)
root.left    = (node_1  = Node.new(1, root))
node_1.left  = (node_2  = Node.new(2, node_1))
node_2.right = (node_3  = Node.new(3, node_1))
node_3.left  = (node_4  = Node.new(4, node_3))

node_1.right = (node_5  = Node.new(5, root))
node_5.left  = (node_6  = Node.new(6, node_5))
node_6.right = (node_7  = Node.new(7, node_5))
node_7.right = (node_8  = Node.new(8, node_5))
node_8.left  = (node_9  = Node.new(9, node_8))
node_9.right = (node_10 = Node.new(10, node_8))
node_8.right = (node_11 = Node.new(11, node_5))

node_5.right = (node_12 = Node.new(12, root))
node_12.left = (node_13 = Node.new(13, node_12))

tree = Tree.new(root)
tree.print_with_constant_space

我希望它有帮助...

于 2014-12-24T01:51:21.633 回答
0

您将不得不按顺序遍历树。在同一本书中，在处理二叉搜索树一章的第一组练习中有一个提示。去引用：

有一个使用堆栈作为辅助数据结构的简单解决方案和一个更复杂但优雅的解决方案，它不使用堆栈但假设可以测试两个指针是否相等。

你可以在这里找到一个实现：http: //tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/

于 2017-01-02T16:56:46.483 回答