0

ルビーで実装されたツリーデータ構造があります。解析ツリーを表すために使用しています。

ご想像のとおり、多くのノード オブジェクトがあり、それぞれに有用な値とその子ノードへの参照の配列が含まれているため、機能します。

私は非常に単純で、次のように動作するツリーをトラバースするメソッドを作成しました。

def depth_first_traversal(node, &block) 
    if(node.has_children?)
        depth_first_traversal(node.children[0], &block) 
        yield node 
        depth_first_traversal(node.children[1], &block)
    else
        yield node  
    end
end

問題は、各ツリーに対して、ルート ノードへの参照のみを明示的に保持していることです。ここまでは、再帰トラバーサルを使用して他のすべてのノードにアクセスしてきました。

ここで、ツリー内のノードの値を変更する必要がありますが、その方法がわかりません。このトラバーサルを変更して、ツリー内の各要素への参照を渡すだけでなく、それらを変更できるようにするにはどうすればよいですか?&block?

--- 編集: ---
詳細が不足していることをお詫びします。質問を幅広く有用なものにしようとしていました。

ツリー内のノードの「値」は、ノード オブジェクトの各インスタンスのいくつかのインスタンス変数です。それら@valueを と と呼びましょう@type。それらには getter メソッドと setter メソッドがあります。

ツリーはバイナリ ツリーですが、後で変更される可能性があります。また、それが私が苦労している問題の側面ではないと思います。

私のツリーは明示的に Node を作成し@rootます。ツリー内の他のすべてのノードはループで作成されます。したがって、典型的なノードは、たとえば「ルートの子の子」としてアクセスでき、他の方法ではアクセスできません。

つまり、このポインターの構造を検索することが、ノードにアクセスする唯一の手段です。ruby が排他的に値を渡す場合、(上記のメソッドのように) 生成される値は、オブジェクト自体ではなく、このオブジェクトのコピーになります。

したがって、このツリーだけでなく、任意のツリーの値を変更する方法について混乱しています。

4

1 に答える 1

0

私があなたを正しく理解していれば、おそらく次のようなことができるでしょう：

def df_tree_map(node, &block)
    if(node.has_children?)
        df_tree_map(node.children[0], &block)
        node = yield node
        df_tree_map(node.children[1], &block)
    else
        node = yield node
    end
end

明らかに、これはツリー構造に影響を及ぼしますが、それは利点になる可能性があります。ただし、ここで重要な点は、古いものの代わりにノードを返す必要があるということです。たとえば、ノードには本質的に子があるため、文字列を返すことは Array#map のようには機能しません。

もう 1 つの解決策は、map 関数がノードの内容を変更できるようにすることですが、構造は変更できません。インスタンス変数ノードもアクセスできるように投稿しなかったので、ここで少し自由にしていますが、それは十分に理にかなっているはずです:

def df_tree_map(node, &block)
    if(node.has_children?)
        df_tree_map(node.children[0], &block)
        node.contents = yield node.contents
        df_tree_map(node.children[1], &block)
    else
        node.contents = yield node.contents
    end
end

ここでは、ノード自体をブロックに渡すのではなく、コンテンツを渡します。このように、マップによってツリー構造を変更することはできません。Array#map 関数との一貫性が向上しているように見えますが、探していることを実行できない可能性があります。

于 2012-12-08T00:58:25.480 に答える