1

最小の深さを持つリーフノードを取得する必要があります。各ノードに追加情報を保存せずにそれを行うための良い方法を考えることはできません。どうもありがとうございました。

4

2 に答える 2

2

ブルートフォースソリューションは、最初に見つかったリーフで終了する幅優先探索です。これは、再帰的よりも反復的に実装する方が簡単です。

たとえば、「幅優先対深さ優先」に対する私の回答の擬似コードを参照してください。whileループに別の条件を追加するだけです。

ところで-これにより、最小の深さの葉が得られます。その深さには複数の葉がある可能性があるためです。最小深度の葉のフルセットを取得するのは少し難しいです。反復深化戦略を採用すると思います。

そのノードが1つのレベルであるかどうかを調べます。

3つの選択肢：

最初にノードを見つけて、ツリーを下に検索します。無駄に聞こえますが、その2番目の検索では、レベルと同じ数のノードにアクセスするだけでよいため、非常に高速です。

または、移動しながら追跡することもできます。3つのカウンター、、およびを使用levelCounterしthisLevelCounterますnextLevelCounter。新しいノードに移動するたびにデクリメントthisLevelCounterし、ゼロに達するとレベルを下げます。

levelCounter++
thisLevelCounter = nextLevelCounter
nextLevelCounter = 0

検索リストに子ノードを追加するたびに、をインクリメントしますnextLevelCounter。新しい子ノードの増分を保存するたびnextLevelCounter

最後に、反復深化戦略は、成功レベルを無料で提供し（反復によって検出されます...）、幅優先探索と同じ順序のパフォーマンス（わずかに高い乗数）を持ちます。

于 2011-11-04T00:06:20.280 に答える
0

ここにコードバージョンがあります（エラーチェックを見逃していないことを願っています）：

void min_leaf(node_t *t, int *min, int lev, node_t **n) {
    if (!t) {
            return;
    }   

    if (lev > *min) {
            printf("Back from %d at lev %d, min: %d already found\n",
                            t->key,
                            lev,
                            *min);
            return;
    }   

    if (!t->left && !t->right) {
            if (*min > lev) {
                    *min = lev;
                    *n = t;
            }   
    } else {
            min_leaf(t->left, min, lev+1, n); 
            min_leaf(t->right, min, lev+1, n); 
    }   
}

void bst_print_min_leaf(bst_t* bst) {
    int min = 10000; /* Replace it with some really large number */
    node_t *minn = NULL;

    min_leaf(bst->root, &min, 0, &minn); /*level: root is level 0 */
    if (minn) printf("min leaf is at depth: %d: (%p:%d)\n", min, minn, minn->key);
}
于 2013-03-25T08:31:41.357 に答える