1

説明: 指定された二分木について

              +---+
              | 9 |
              +---+
             /     \
         +---+     +---+
         | 7 |     | 6 |
         +---+     +---+
        /     \         \
    +---+     +---+     +---+
    | 3 |     | 2 |     | 4 |
    +---+     +---+     +---+
             /               \
         +---+               +---+
         | 5 |               | 2 |
         +---+               +---+

合計は次のように計算されます。

1 * 9 + 2 * (7 + 6) + 3 * (3 + 2 + 4) + 4 * (5 + 2) = 90

これを解決するための私のアプローチは、各ノードのレベルを見つけてノードのキーで乗算し、左右のサブツリーのすべてのノードに対して再帰的に行うことです。

int weightedSumAtAllLevels(BTNode node) {
    if (node != null)
        return levelSumOfLeftSubTree(node.getLeftChild())
                + levelSumOfRightSubTree(node.getRightChild())
                + node.getKey();
    else
        return 0;
}

int levelSumOfLeftSubTree(BTNode tmp) {
    if (tmp == null) {
        return 0;
    } else {
        int level = levelOfNode(tmp);
        return level * tmp.getKey()
                + levelSumOfLeftSubTree(tmp.getLeftChild());

    }
}

int levelSumOfRightSubTree(BTNode tmp) {
    if (tmp == null) {
        return 0;
    } else {
        int level = levelOfNode(tmp);
        return level * tmp.getKey()
                + levelSumOfRightSubTree(tmp.getRightChild());
    }
}
int levelOfNode(BTNode node) {
    if (node == null)
        return 0;
    else
        return 1 + levelOfNode(node.getParent());
 }

うまくいかないようです。このソリューションに欠陥があることはわかっていますが、修正できません。何か助けはありますか？提案？

4

3 に答える 3

2

主な問題は、左に行き始めると、左に進み続けることです。左の子の右の子を見ることは決してありません。

ノードとそのレベルの両方を取る単一の関数を使用して加重合計を計算できます。これにより、実装が大幅に簡素化され、正しく実行しやすくなります。

これはおおよその実装です（私はテストしていません）：

int weightedSumAtAllLevels(BTNode node, int level) {
    if (node != null) {
        return level * node.getKey() +
               weightedSumAtAllLevels(node.getLeftChild(), level + 1) +
               weightedSumAtAllLevels(node.getRightChild(), level + 1);
    } else {
        return 0;
    }
}

ルート ノードに対してこれを呼び出す方法を理解するための演習として残します。

于 2013-10-26T07:20:07.277 に答える
1

ルートから始めて、レベル = 1 に初期化するだけです。

sum = root.key()*level + weightedSum( root.left(), level + 1 ) + weightedSum( root.right(), level + 1 );
于 2013-10-26T07:21:12.570 に答える
0

ヒントとして.. ツリーに対して DFS トラバーサルを実行します。次に、深さごとにノードの値を合計し、深さ + 1 を掛けます。

于 2013-10-26T07:19:41.103 に答える