1

私は最後のcsクラスにほとんどきしみませんでした、そして今私はデータ構造にいます。私は二分木構造を最初から構築していますが、イテレータがどのように機能するかについて少し混乱しています。二重リンクリストでどのように機能するかは理解していますが、これがどのように機能するかはわかりません。

4

6 に答える 6

1

他のすべての回答は、ツリー構造に反復子を実装する方法に関する技術的な議論です。しかし、あなたの質問を理解しているように、実装だけでなく、ツリー トラバーサルの概念の仕組みを理解するのに苦労しているようです。つまり、ツリー トラバーサルを「理解」することはありません。おそらく何よりも役立つのは、バイナリ ツリー、鉛筆、紙 1 枚をトラバースするための優れた擬似コード アルゴリズムを取得し、例を作成することです。単純なバイナリ ツリーを構築し、疑似コードを自分で機械的にたどってトラバースします。スタックを書き出すために、おそらく 2 枚目の紙を使用する必要があります。つまり、サブ関数が戻るのを待っているために呼び出されている途中のすべての関数の状態です。

これを行っている間は、ツリーは非常にエレガントな構造であることを覚えておいてください。非常に複雑に見えるかもしれませんが、すべてのノードで単純です。ツリー内のすべての要素に対して操作を実行するには、ツリーのルートでその操作を実行し、それ自体がサブツリーのルートであるそのルートの各子に対して操作自体を呼び出します。自分で例を考えてみることは、再帰を理解し、受け入れられるようになるのに大いに役立ちます。難しいと感じても、当惑しないでください。再帰は奇妙です。最初は難しい概念ですが、木を理解して操作する必要があります。

開始に使用できるツリーの例 (ASCII アート) を次に示します。

      ふ
    / \
   / \
   DH
 / \ / \
 ベギ
/ \
交流

そして、すべての文字を正しい順序で走査するために使用できる単純な擬似コード アルゴリズム。

プロシージャ トラバース(ノード)
    ノードが null でない場合:
        traverse(node.left)
        node.letter を書く
        traverse(node.right)
    そうしないと：
        何もしない

単純なツリーから始めることもできます。ツリーがノード D、F、および H のみで構成されている場合はどうなるでしょうか? Fだけだったら？ヌル？これらの簡単な例を試して、より大きなツリーに取り組んでください。これを一貫して正しく行う方法を理解するまでには、イテレータの実装で何が起こっているかについて本当に良い感触を得られるだけでなく、再帰の力についての理解が深まるでしょう。

于 2009-05-06T03:07:37.780 に答える
0

「Iterator」とはどういう意味ですか？ツリーを繰り返す必要がある場合は、再帰的に行うことができます：http: //en.wikipedia.org/wiki/Tree_traversal#Sample_implementations

C＃やJavaのようにIEnumeratorインターフェイスを提供する必要がある場合、またはスタックスペースを節約したい場合は、次を使用します。http: //en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal C＃でyieldを使用するか、簡単に変換できます。反復子に必要な「GetNext」メソッドにループします。

于 2009-05-06T00:34:28.320 に答える
0

再帰的に実行できます。根元から始めて次に進む場所には2つの選択肢があり、その後は2 ^ n倍になるので、葉から葉へとどのように移動するかを頭の中で想像しようとしています。これがどのように機能するかというこの順序は、私を混乱させるものです。

于 2009-05-06T00:47:33.123 に答える
0

二分木では、すべてのノードが何らかの値を格納し、たとえば左と右のように 2 つの子を持ちます。ツリーをトラバースする 1 つの方法は、上から開始し、左側の子をトラバースし、このノードの値を確認してから、右側の子をトラバースすることです。

子をトラバースするとは(再帰的に) を意味します: 1) 左の子をトラバースする 2) ノードの値を調べる 3) 右の子をトラバースする

これは深さ優先トラバーサルであるため、各ノードについて、最初に左の子の値を「使用」または「参照」し、次に現在のノードの値、最後に右の子の値を使用します。

幅優先トラバーサルの場合、ルートから開始し、ノードの値を確認してから、その子 (存在する場合) をキューにプッシュします。次に、キューにノードがある間ループし、キューの先頭からノードを取得して繰り返します。その値を確認し、子がある場合はキューの最後にプッシュします。

Python での例:

#!/usr/bin/env python

    class Node:
        def __init__(self, val = 0):
            self.value = val
            self.left = None
            self.right = None

        def __str__(self):
            return "%d" % (self.value)

    def dfs(node = None):
        if node is None: return

        dfs(node.left)
        print node
        dfs(node.right)

    def bfs(root = None):
        if root is None: return

        nodes = []
        nodes.append(root)

        while len(nodes):
            current = nodes[0]
            print current
            nodes.remove(current)

        if current.left is not None:
            nodes.append(current.left)
        if current.right is not None:
            nodes.append(current.right)

    def main():
        root = Node(0)
        root.left = Node(10)
        root.right = Node(20)

        l = root.left
        l.left = Node(100)
        l.right = Node(101)

        r = root.right
        r.left = Node(200)
        r.right = Node(201)

        dfs(root)
        bfs(root)


    if __name__ == '__main__':
        main()



# example tree constructed:
#            0
#      10        20
#  100   101  200  201

# dfs (depth first) traversal:
# 100
# 10
# 101
# 0
# 200
# 20
# 201

# bfs (breadth first) traversal:
# 0
# 10
# 20
# 100
# 101
# 200
# 201
于 2009-05-06T01:24:29.807 に答える
0

データ構造クラスでも同じ問題が発生しました。

私の解決策はかなり単純です。

ツリーを再帰的にトラバースしますが、アクセスした各ノードを別のコレクションに格納してから、その新しいコレクションを反復します。そうすれば、イテレータを書くのに難しいことは何もありません。

私は個人的にスタックを使用することを選択しましたが、単純な配列、またはリンクされたリストを使用することもできます (これについては既に経験があると述べました)。

于 2009-05-06T01:41:23.993 に答える
0

ツリーを反復処理するには、主に 2 つの方法があります。反復ツリー ウォーキングで、それを行う方法のサンプル Python コードをいくつか投稿しました。

于 2009-05-06T01:03:35.237 に答える