4

深さ優先検索を実行して、ツリーを反復処理するこのコードがあります。すべての要素が 1 回だけ処理されます。とても良い。

-(void)iterateOverTree:(TreeNode *)node
{
    NSMutableArray * elements = [NSMutableArray array];
    [elements addObject:node];

    while([elements count])
    {
        TreeNode * current = [elements objectAtIndex:0];
        [self doStuffWithNode:current];
        for(TreeNode * child in current.children)
        {
            [elements addObject:child];
        }

        [elements removeLastObject];
    }
}

BUT: グラフの現在の深さを追跡するにはどうすればよいですか? 深さのレベルを知る必要があります。たとえば、次のノードがあります。

A には子 B、J がいます。B には子 C があります。C には子 D があります。D には子 E、F、I があります。

A が深さレベル 1 の場合、B は 2、C は 3 です。

再帰を使用すると、現在の深度レベルを追跡するのが非常に簡単になりました。自分自身を呼び出す前に変数をインクリメントし、自分自身を呼び出した後にデクリメントします。

しかし、ここでは、この空想的な while ループを使用することはできません。再帰のようにボックス内のボックス内にボックスはありません。

プロパティ (またはインスタンス変数) を TreeNode オブジェクトに追加する必要はありません。これは、あらゆる種類のオブジェクト グラフに対して一般的な方法で再利用できるはずだからです。

これを行う方法を知っている人はいますか？訪問したノードを追跡するために別の配列を導入する必要がありますか?

4

4 に答える 4

1

あなたが実際にやっていることはBFSだと思います。あなたはリストを扱っています。DFS を実行するには、スタックを使用する必要があります。

これは、深度トラックに役立つ可能性があります。(親の) ベクトル p を調べることができます。

于 2011-04-26T10:11:19.030 に答える
1

深さも積み重ねる必要があると思います。これは、再帰的なバージョンがあれば、とにかく実際に行ったであろうことです。現在行っているように、明示的なスタックの代わりに呼び出しスタックを使用していたので、ストレージが「見えない」だけです。

それが役立つ場合は、配列をスタックの代わりにキューとして使用することで、深さ優先検索を幅優先検索に簡単に変換できます。(removeLastObject の代わりに removeFirstObject を実行するだけです。) そうすると、常にノードを深さの減少しない順に見ることがわかります。ただし、正確な深度が必要な場合は、現在の深度をいつインクリメントする必要があるかを追跡するために、ストレージを追加する必要があると思います。

アップデート：

代わりに、ノードの親ポインターをたどってツリーをバックアップする場合は、スタックをまったく使用せずに DFS を実行できるはずです。これにより、深さを簡単に維持できます。ただし、子供を再スキャンして自分がどこにいるかを調べることで、線形時間の最悪の場合の複雑さを壊さないように注意する必要があります。

親ポインターがない場合は、親を追跡するのに十分な情報をスタックできるはずです。しかし、これは、現在行っているよりも多くの情報をスタックに入れることを意味するため、深さを直接スタックするよりも大きな改善にはなりません。

ところで、あなたのアルゴリズムを注意深く見てみると、次の現在のノードを取得するときに、配列の間違った側を見ていませんか? 次のように動作するはずです。

push root
while stack not empty:
   current = pop
   push all children of current
于 2011-04-26T09:33:55.767 に答える
1

私はあなたの表記法を理解していませんが、私が正しく読めば、ノードを処理し、すべての子をやるべき仕事のリストに追加します。

その部分を再帰を使用するように変更できれば、再帰の深さになるため、ツリーの深さを追跡できます。

したがって、子ノードを追加する代わりに、子ノードごとに再帰します。

h番目

マリオ

于 2011-04-26T09:21:05.730 に答える
-1

BFS を実行していると仮定すると、最も簡単な方法は、ノード キューをミラーリングする深さの別のキューを導入することです。深さをゼロに初期化します。ノードキューにプッシュするたびに、現在の深さ + 1 を深さキューにプッシュします。

于 2014-10-09T02:30:46.420 に答える