Binary Tree for circuits

Question

i need some help with this problem.

I have a binary tree stucture which shows all paths between 2 nodes "1" and "10" as shown in the diagram. and the interconnections between the node(i.e. edges) have certain weights.

Now can anybody sugest me an algorithm or a flow as to how to calculate the following.

now let us take paths from "1" to "10" "a) 1 to 2 to 3 to 10" "b) 1 to 2 to 4 to 8 to 10" "c)1 to 2 to 4 to 7 to 10 etc"

now the way the calculation is done is liek a series/parallel circuit.

wherevr the node branches into 2 I need to calculate the series resistance values

for example if i just consider two paths" a) 1 to 2 to 3 to 10 and 1 to 2 to 4 to 8 to 10"

we can see that there is a branch at 2 .. so i add all edge values from" 2 to 3 to 10" and "2 to 4 to 8 to 10 "and then multiply these two sums and then add value from "1 to 2" to get the overall value.

this has to be done over the entire tree.. any ideas as to how to go about implimenting this in C ??

Image can be found here : https://i.stack.imgur.com/PlXiT.png

See http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices Breadth first search — eqzx, Jun 13 '12 at 22:34
How about 1-2-4-7-10? Wouldn't it change the result of your example calculation? — jpalecek, Jun 13 '12 at 22:34
yup.. that was just an example.. the algo would need to take into account all routes — rav3451, Jun 13 '12 at 22:38
@nrhine.. i have already computed the paths between the two nodes.. I am looking for an algorithm that will help me perform the calculations.. — rav3451, Jun 13 '12 at 22:43

score 1 · Accepted Answer · answered Jun 13 '12 at 22:43

I take it that you want to calculate some esoteric value for a tree, which is defined on each node by some calculation based on the subtrees' values. That's not that hard, using a recursive function:

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;
}

I'm not sure that I understand your problem, but that should give you the idea.

Binary Tree for circuits

1 Answers1