1

次のアルゴリズムを実装しようとしています。

Fitch のアルゴリズム (1 文字シーケンスの場合):

ステップ 1: 各リーフ ノード n に対して、リーフに割り当てられた文字を含むセット Sn を作成します。

ステップ 2: 子 u と v を持つ内部ノード n ごとに、次の集合 Sn を作成します。 • Su ∩ Sv が空でない場合は、Su ∩ Sv。• Su ∩ Sv が空の場合、Su U Sv。

ステップ 3: 親 p を持つ内部ノード n ごとに、n.seq に次の文字を割り当てます。

入力として二分木が与えられます。

ステップ 1 を完了したので、バイナリ ツリーを介してポストオーダー ナビゲーションを再帰的に実行して、すべてのノードにセットを割り当てる必要があります。これをどのように開始するのだろうか？

事前順序再帰を使用したツリーのナビゲートは、次のように行われます (これは、ツリー内にあるリーフの数によって決定されるツリーの長さを計算する単なる例です。リーフ = 子なし):

def __len__(self):

     if self.isLeaf():
        print('base case - reached leaf!')
        return 1

    for t,w in self.children:  
        print('not leaf so sent through loop')
        numLeaves += len(t)

    return numLeaves
4

1 に答える 1

1

それは非常に簡単です。左右の子がなくなった後でのみ、ノードを訪問済みとしてマークします。ルート ノードにアクセスした後、アルゴリズムは終了します。再帰を使用すると、アルゴリズムははるかに簡単になります。

アルゴリズムに適したセットを取得するには、ポスト オーダー トラバーサルで割り当て文字列 (葉の場合は 1 文字) または空白文字 (右または左の子がない場合) を返すようにします。

ポスト オーダー関数で、返された文字列を追加してから、追加された文字列を返します。

http://en.wikipedia.org/wiki/Tree_traversal#ポストオーダー

于 2013-02-28T20:30:47.950 に答える