4

次の質問は、私のインストラクターが数年前に行ったテストに出てきました。彼は答えを提供しましたが、満足のいく説明を提供しませんでした。このトピックをグーグルで検索しましたが、あまり見つかりませんでした。コミュニティがこの概念を理解するのに役立つことを願っていました。

バイナリ ツリー内のすべての整数の合計を見つけるために、どのタイプのトラバーサルが使用されますか?

(A) 幅優先
(B) 深さ優先インオーダー
(C) 深さ優先ポストオーダー
(D) 深さ優先プリオーダー

私のインストラクターは、答えは (C) 深さ優先ポスト オーダーだと言っていますが、その理由がわかりません。それらはすべて機能するようです。あなたが持っているかもしれない洞察をいただければ幸いです。

ありがとう。

編集：インストラクターが答えを（C）だと思った理由をようやく理解しました。

次のように、加算をすべて 1 つのステートメントにまとめて sum 関数を記述するとします。

    int addup(Node n)
    {
        if (n == nil) return 0;
        return addup(n.left) + n.value + addup(n.right);
    }

トラバーサルは、合計内の項の順序に関係なく、ポスト オーダーになります。これは、加算が行われる前に 2 つの関数が最初に評価されるためです。ただし、キース・ランドールが回答で示したように、事前順序または順序どおりのトラバーサルを強制することは簡単です。

4

1 に答える 1

3

sum は結合的で対称であるため、どのような走査順序でも機能します。たとえば、深さ優先順:

int addup(Node n) {
    if (n == nil) return 0;
    int sum = addup(n.left);
    sum += n.value;
    sum += addup(n.right);
    return sum;
}

すべてのトラバーサルは、簡単な合計の実装を認めています。

于 2013-02-27T04:48:46.067 に答える