0

各エッジのコストが1である最小コストでバイナリツリーをトラバースしたいと思います 。ツリーの各ノードにアクセスすると、トラバースが完了します。

たとえば、次のツリーのトラバーサルの最小コストは13です。

       *
      / \
     *   *
    / \   \
   *   *   *
  /   /     \
 *   *       *

次のツリーのトラバーサルの最小コストは12です。

        *
       / \
      *   *
     / \   \
    *   *   *
   /     \
  *       *
 /
*
4

1 に答える 1

7

ツリーをトラバースするコストはn-1、nノードの数です。

すべてのツリーには正確にエッジがあるため、これは当てはまりますn-1。すべてのノードにアクセスするには、それらすべてを使用する必要があります。

正確には、次の3つのステートメントは、ノードを持つグラフ Tと同等であることがわかっています。n

  1. Tはツリーです（サイクルなしで接続されています）
  2. Tは接続されており、n-1個のエッジがあります
  3. Tにはサイクルがなく、n-1個のエッジがあります

上記から、ツリーでは、すべてのノードに到達するために、すべてのエッジを使用する必要があると結論付けることができます（サイクルがないため、冗長なエッジがないため）-そしてn-1それらは正確にあります。

編集：

あなたの例から、各エッジから戻る回数もカウントしているようです（つまり、一部のエッジは2回カウントされます）。

この場合、最適なソリューションは次のようになります。

cost = (n-1)*2 - height

説明/証明のガイドライン： ツリーには正確にエッジ
があります。n-1ルートから最も深いノードにつながるものを除いて、それぞれが正確に2回トラバースされます。
最後のブランチを除いて、各ノードから戻るため、各エッジ（上記を除く）を正確に2回使用する必要があります。
最後のブランチには正確にheightエッジがあるため、合計でcost = (n-1)*2 - height

それは基本的にあなたが得たものと同じであることに注意してください：

height + 2*(n-1-height) = height + 2(n-1) -2height = 2(n-1) - height
于 2013-01-05T09:20:39.310 に答える