-1

この問題について助けが必要です。

図に示すように、2つのノード「1」と「10」の間のすべてのパスを示す二分木構造があります。また、ノード（つまりエッジ）間の相互接続には特定の重みがあります。

これで、次の計算方法に関するアルゴリズムまたはフローをだれでも推測できます。

ここで、「1」から「10」へのパスを取りましょう。「a）1から2から3から10」「b）1から2から4から8から10」「c）1から2から4から7から10など「」

現在、計算が行われる方法は、直列/並列回路のようです。

ここで、ノードは2に分岐します。直列抵抗値を計算する必要があります。

たとえば、2つのパスを考えた場合 "a）1から2から3から10および1から2から4から8から10"

2 ..に分岐があることがわかります。したがって、「2から3から10」および「2から4から8から10」までのすべてのエッジ値を加算し、これら2つの合計を乗算してから、「1から」までの値を加算します。全体的な値を取得するには2"。

これはツリー全体で実行する必要があります。これをCで実装する方法についてのアイデアはありますか？

画像はここにあります：http：//i.stack.imgur.com/PlXiT.png

4

1 に答える 1

1

サブツリーの値に基づいた計算によって各ノードで定義されるツリーの難解な値を計算したいと思います。再帰関数を使用すると、それほど難しくありません。

struct node {
  struct node* left, *right;
  int left_weight, right_weight; /* or something*/
};

int calculate_it(struct node* root)
{
  /* do the calculation */
  if(root->left && root->right) {
    int l = calculate_it(root->left) + root->left_weight;
    int r = calculate_it(root->right) + root->right_weight;
    return l*r;
  } else if(root->left || root->right) {
     return root->left ? calculate_it(root->left)+root->left_weight :
       calculate_it(root->right)+root->right_weight;
  }
  return 0;
}

私はあなたの問題を理解しているかどうかわかりませんが、それはあなたにアイデアを与えるはずです.

于 2012-06-13T22:43:56.817 に答える