6

「アルゴリズム入門」という本を読んでいます。多くの方がご存知だと思います。かなり難しいと思われる質問にぶつかりました。

nノードのバイナリツリーが与えられると、各ノードのキーを出力するO（n）時間の非再帰的プロシージャを記述します。ツリー自体の外側に一定の余分なスペースを使用し、手順中に一時的であってもツリーを変更しないでください。

私はこのような別の質問があることを見ました：余分なメモリなしでO（n）時間でバイナリツリーをトラバースする方法ですが、主な違いはツリーを変更できないことです。訪問した旗を使うことを考えていましたが、まだ正しい解決策を見つけていません。それは私には見えない明らかなことかもしれません。この問題を解決するアルゴリズムをどのように考案しますか？答えへのいくつかのポインタでさえいただければ幸いです。

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

あなたは木の順番に歩く必要があります。同じ本の中で、二分探索木を扱う章の最初の一連の演習にヒントがあります。引用するには：

補助データ構造としてスタックを使用する簡単なソリューションと、スタックを使用しないが2つのポインターが等しいかどうかをテストできることを前提とするより複雑で洗練されたソリューションがあります。

ここで実装を見つけることができます：http：//tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/

于 2017-01-02T16:56:46.483 に答える