3

わかりました、私は葉の束10、9、7、8を与えられ、私はそれらから合計ツリーを作成する必要があります ここに画像の説明を入力してください

丸で囲んだものの合計を見つける必要があります。

問題は実際には重量の問題であり、一度に2つの要素を選択してそれらを追加できます。それらの合計重量は要素を結合するために行われる作業であり、最小量を実行しながらすべての重みが結合されるまでこれを継続する必要があります。動作しますが、これが解決方法だと思うので、これに変えました。

これはこの問題を解決するための最良の方法ですか、それともより良い方法がありますか？

このツリーを作成し、それらのノードの合計を計算するための最速の方法は何でしょうか？

4

3 に答える 3

0

スタック マシンを使用します。スタックに 2 つの要素が含まれるまで葉を押します。それらの要素をポップし、それらを追加 (sub、mult、div など) し、結果をプッシュします。入力に要素がなくなるまで、これを続けます。最終結果はスタックの一番上にあります。このアルゴリズムは、合計ツリーが行うのと同じ順序で算術を行います。

code                stack
--------------------------
push 10             10$        
push 9              9, 10$     

pop a               10$
pop b               $
push a+b            19$

push 7              7, 19$
push 8              8, 7, 19$

pop a               7, 19$
pop b               19$
push a+b            15, 19$

pop a               19$
pop b               $
push a+b            34$

done                34$
于 2012-04-28T23:20:43.493 に答える
0

貪欲な解決策：

  1. すべての葉を優先キューに入れます (最小重量が最初に出てきます)。
  2. キューに複数のツリーが含まれている場合、2 つの最小重みツリーを取り出して結合し、ジョイント ツリーをキューに挿入します。
  3. キューに含まれるツリーが 1 つだけの場合、それが解決策です。

貪欲な解決策は機能します：

葉から構築された任意の二分木が与えられると、各葉depth*weightは総作業/コストに貢献します。(葉の深さは、根から葉までのパスの長さです。たとえば、

   18
  /  \
  3   15
/  \ /  \
1  2 4  11
       / \
       5  6

リーフ 1、2、および 4 の深さは 2、リーフ 5 および 6 の深さは 3 です。)

したがって、ツリーの特定の形状について、最も軽い葉が最も深いときに最小の総コストが得られます。したがって、最初のステップで 2 つの最も軽い葉を新しいツリーに結合するときに、最小コスト ツリーに到達します。

いくつかの葉がすでに結合されている場合、ツリーを構築する総コストは (これまでのコスト) + (非シングルトン ツリーを葉として考慮した最も安価なツリーを構築するコスト) です。

したがって、最小コスト ツリーでは、上記の理由により、2 つの最も軽い「葉」が最も深いレベルにある必要があるため、これらを結合して新しいサブツリーを形成できます。

于 2012-04-28T23:29:32.113 に答える
0

Javaを使った実装はこちら

public static int sumTree(BinaryTreeNode<Integer> node) {
    if (node == null) {
        return 0;
    }
    int oldVal = node.getData();
    node.setData(sumTree(node.getLeft()) + sumTree(node.getRight()));

    return oldVal + node.getData();
}

ここにテストケースがあります

@Test
public void sumTreeTest() {
    BinaryTreeNode<Integer> bt = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{8,-2,-4,10,7,6,5}, new Integer[]{8,-4,-2,7,5,6,10});
    BinaryTreeUtil.sumTree(bt);
    List<Integer> result = new ArrayList<Integer>();
    BinaryTreeUtil.printInOrder(bt, result);
    assertThat(result.toArray(new Integer[0]), equalTo(new Integer[]{0, 4, 0, 20, 0, 12, 0}));
    //System.out.println(Arrays.toString(result.toArray()));
}
于 2016-04-06T16:28:13.273 に答える