returning and using multiple tree structures in a recursive function

Question

I have a function get_trees() that operates on a complex tree structure T and returns two component tree structures A and B. The only way I have been able tot get this to work is to create a new structure C with pointers to A and B, which is then passed as a parameter to the function and is also a return value:

typedef struct Composite {
itree *A;
itree *B; 
} composite;

composite *get_trees(complextree *T, itree *A, itree *B, composite *C);

Root nodes of trees A & B are initialized in another function:

itree *A = new_itree(0);
itree *B = new_itree(0);
A->n     = T->a;
B->n     = T->b;
composite *C;
C = get_trees(T, A, B, C);

get_trees() walks down branches of complextree T, allocates and populates nodes of A and B and recursively calls itself on subodes. Simplified code:

//code for allocating subnodes of A and B     
if (T->nodes != NULL){
    for (i=0; i< T->nn; i++){
    //code for computing p & q
    C = get_trees(T->nodes[i], A->nodes[p], B->nodes[q]);
    }
}

The code works fine. However it seems very ugly.

(1) C has no intrinsic meaning and ie being used to allow return of multiple values. Is there an alternative?? Something along the following lines:

(2) Is it possible to write the recursive function with the following signature:

void get_trees(T, A, B);

Is seems that if I pass the root nodes of A & B as parameters and subnodes are allocated within the recursive function, then there is a continuous chain of command so to speak and the whole tree should be available when the recursive call completes. It did not work for me, so it must not be allowed. I would appreciate if someone could explain why that is the case, or if a more elegant solution is possible??

Thanks and happy holidays. ~RT

Answer 1

What you have done is the only way to return multiple pointer values as the return value of a function. But it's not considered good form.

Good form would be to declare your function has having out parameters as well as in parameters and using the return value to indicate success or failure. like this

bool get_trees(complextree *T, itree *A, itree *B, composite *C, itree ** AOut, itree** BOut);

Answer 2

yeah passing a pointer to the callers composite would let the function use that to store results. course it's vital to create the composite object first, on the stack or heap...

   composite c;
   get_trees(&c);

   composite *c = malloc...
   get_trees(c)

of course the function could actually return a struct which will get copied to the caller, but i would only use that style in limited cases...

Answer 3

Here is a simpler version of the question. Suppose we have a node:

typedef struct Node {
    int n; // number of sub-nodes
    int i; // data
    node  **nodes;//subnodes
} node;

Now the following code clones the tree structure with data-values doubled (without any error checking).

node *double_tree( node *A, node *B ) {
  if ( B == NULL ) {
    B = (node*) calloc( 1, sizeof (node ) );
  }
  B->i = 2 * A->i;
  B->n = A->n;
  if ( A->nodes != NULL ) {
    B->nodes = (node **) calloc( 1, A->n * sizeof (node* ) );
    int ii;
    for ( ii = 0; ii < A->n; ii++ ) {
        B->nodes[ii] = double_tree( A->nodes[ii], B->nodes[ii] );
    }
  }
  return B;
}

My original problem involved two variations:

(a) There were multiple return trees (say double_tree, square_tree).

(b) Structure of the return trees were different from the input tree.

It seems that the core problem is that "a structure allocated inside a function must be 'returned' as a function output as a pointer", just passing the pointer as a parameter does not do the trick. I am hoping I am wrong and that there is a better way of doing this.

Thanks again for the assistance, Russ