0

特定の BST の深さの合計 [ルートのすべての子の個々の深さの合計] を計算するのが困難です。ツリーのノードの総数があり、ツリーの平均深さを計算しようとしています。この深さの合計が必要です。

再帰と私はうまくやっていけません..私はこの問題が非常に難しいと感じています. 可能であれば、再帰的な解決策を見たいと思います。

ノート：

アクセサー Node.getLeft() と Node.getRight() を作成しました

4

5 に答える 5

4

ツリーをトラバースするときに深度カウンターを保持し（必要に応じてツリートラバーサルを検索）、ノードに到達するたびにカウンターの値を追加する必要があります。次に、ノードの数で割ります。

これは宿題のように見えるので、これ以上詳細な解決策は提供していません。

于 2009-12-09T20:09:26.817 に答える
2

私が一枚の紙にBSTの写真を提示したとしたら、これを手作業でどのように標準的に行うかを考えてください。ノードにいるとき、どのような情報を追跡する必要がありますか？特定のノードの高さをどのように見つけますか？

ここから、これを擬似コードに変換するか、Javaに直接変換してみてください。問題が発生した場合は、ユーザーがサポートできるようにコメントしてください。

于 2009-12-09T20:08:33.493 に答える
0

すべての葉のノードにアクセスして、それらがどれだけ深いかを把握する必要があります。これは次のことを示唆しています。

ノード訪問関数に追加の引数を与えます。どこに向かっているのかだけでなく、どれだけ深いのかを知る必要があります。呼び出されるたびに、さらに深くなるように呼び出されるため、ノードの訪問者は、呼び出し元から取得した深度番号をインクリメントするだけで済みます。

これで、次の2つのいずれかが発生する可能性があります。

  • 見つけたノードはリーフノードです。つまり、子はありません。この場合、訪問者はその深さを発信者に返す必要があります。ええ、それは発信者から取得した番号+1を返すだけです。

  • または、リーフノードではありません。その場合、1人または2人の子供がいます。子供から発信者にこれらの深度レポートを戻す必要があるため、子供から返された深度の合計を返すだけです。

再帰の魔法によって、ルートの訪問者に返される数は、すべての子の深さの合計になります。

平均深度を取得するには、これをリーフノードの数で割る必要があります。これを計算するために2回目のトラバーサルに任せます。1つで行うこともできますが、もう少し複雑になります。

于 2009-12-09T20:26:08.860 に答える
0

これは宿題ですか？その場合は、質問にそのようにタグ付けしてください。

次のようなメソッドを作成できます。

  • ノード参照と深さを引数として持つ
  • 増分の深さ
  • ノードが子ノードでない場合は、左と右を再帰的に呼び出し、それに応じて合計を更新します
  • それ以外の場合は、合計 + 深さを返します

これをツリー内の子の数で割ると、平均の深さが得られます。

于 2009-12-09T20:10:24.303 に答える
0

これは宿題なので、答えだけは言いたくありません。代わりに、単方向リストの長さを再帰的に計算する方法を次に示します。うまくいけば、これが理解できる方法で再帰を示し、そこから外挿して BST 問題を解決できることを願っています。

public final class LL {
    public final int value;
    public LL next;

    public LL(final int value) {
        this.value = value;
    }

    public void add(final int value) {
        if (null == next) {
            next = new LL(value);
        } else {
            next.add(value);
        }
    }

    /**
     * Calculate the length of the linked list with this node as its head (includes this node in the count).
     *
     * @return the length.
     */
    public int length() {
        if (null == next) {
            return 1;
        }
        return 1 + next.length();
    }

    public static void main(final String... args) {
        final LL head = new LL(1);
        head.add(2);
        head.add(3);
        System.out.println(head.length());
        System.out.println(head.next.length());
    }
}
于 2009-12-09T20:57:54.723 に答える