-1

我需要一些帮助来解决这个问题。

我有一个二叉树结构，它显示了 2 个节点“1”和“10”之间的所有路径，如图所示。并且节点（即边）之间的互连具有一定的权重。

现在任何人都可以向我推荐一个关于如何计算以下内容的算法或流程。

现在让我们从“1”到“10”“a）1到2到3到10”“b）1到2到4到8到10”“c）1到2到4到7到10等路径"

现在计算的方式是串联/并联电路。

wherevr 节点分支为 2 我需要计算串联电阻值

例如，如果我只考虑两条路径“a）1 到 2 到 3 到 10 和 1 到 2 到 4 到 8 到 10”

我们可以看到在 2 处有一个分支 .. 所以我将“2 到 3 到 10”和“2 到 4 到 8 到 10”的所有边缘值相加，然后将这两个和相乘，然后将值从“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 回答