Search code examples
ctreechildrenappendchild

C - Nary Tree: error while appending a new child to the tree


I'm developing a Nary Tree in C using a structure like this:

typedef struct sNaryNode { 
     int *data; // Point to the node ’s data
     int n; // The number of children 
     struct sNaryNode **child; // The child list
} NaryNode; 

typedef NaryNode NaryTree;

I can't use a List (as required into the project). I'm able to create the Tree, but when I try to append a new child to the Tree, all the "data" value of the Tree are overwrited with the new value. For example: I create the root with data = 1, then I want to append a new child with data = 2, at the end both the root and the new child have the same "data" value, that is data = 2. I think that the problem is not due to a mistake with pointers management, but since I don't know where I'm wrong, I decided to ask your opinion. Here is the full code:
lm_array2.h

#ifndef lm_array2_h
#define lm_array2_h

typedef struct sNaryNode { 
     int *data; // Point to the node ’s data
     int n; // The number of children 
     struct sNaryNode **child; // The child list
} NaryNode; 

typedef NaryNode NaryTree;
typedef void (*DataFreeFunc) (const void *);

void printArrayTree (NaryTree*);
NaryTree *createNode (int, int*);
void freeTree (NaryTree*, DataFreeFunc);
int appendChild(NaryNode*, int*);
void deleteChild (NaryTree*, int, DataFreeFunc);

#endif

lm_array2.c

#include <stdio.h>
#include <stdlib.h>
#include "lm_array2.h"

void printArrayTree (NaryTree *tree) {
    int d = *tree->data;
    printf("\n %d ", d);
    if (tree->n > 0) {
        int i;
        for (i = 0; i < tree->n; i++) {
            //printArrayTree (tree->child[i]);
            int dd = *tree->child[i]->data;
            printf("\n %d", dd);
        }

    }
    else {
        printf("\n-----\n");
        return;
    }
}

NaryTree *createNode ( int children , int *data) { 
    // Allocate space for a new NaryNode in memory
    NaryNode *node = (NaryNode*) calloc (1 , sizeof (NaryNode) );

    // Set the contents of the NaryNode appropriately
    node->data = data; 
    node->n = children ; 
    node->child = (NaryNode**) calloc ( children , sizeof (NaryNode*) );

    // Return the node we initialized
    return node;
}

void freeTree (NaryTree *tree , DataFreeFunc dFree) {
    unsigned i; 

    // Don’ t try this with a NULL pointer 
    if ( tree == NULL) return; 

    // Free the children recursively 
    for ( i = 0; i < tree->n; ++i ) 
        freeTree ( tree->child [ i ] , dFree); 

    // Free the child array 
    free ( tree->child ); 

    // Free the data if a function is provided 
    if (dFree) dFree( tree->data); 

    // And finally , free the structure 
    free ( tree ); 
}

 int appendChild(NaryNode *root , int *data) {
     // Increment the degree of the node 
     root->n++; 

     // Reallocate the child array (n children in the child array) 
     root->child = (NaryNode**) realloc ( root->child , ( root->n)*sizeof (NaryNode*) );

     // Add the newNode into the child array and increment degree 
     root->child [ root->n - 1] = createNode (0 , data); 

     // Return the index of the child we just inserted 
     return root->n - 1;  
 } 

 void deleteChild (NaryTree *root , int idx , DataFreeFunc dFree) {
     unsigned i; 

     // Delete the child 
     freeTree ( root->child [ idx ] , dFree); 

     // Remove the defunct child 
     for ( i = idx ; i < root->n - 1; ++i ) 
        root->child [ i ] = root->child [ i - 1]; 

     // And finally , reallocate 
     root->n--; 
     root->child = (NaryNode**) realloc ( root->child , ( root->n)*sizeof (NaryNode*) );
 }

main.c

#include <stdio.h>
#include <stdlib.h>
#include "lm_array2.h"
#include "lm_array2.c"

void menu(int*);

int main() {
    NaryTree *aTree = (NaryNode*)malloc(sizeof(NaryNode));
    int choice = 0, value;

    printf("\nEnter the root value: ");
    scanf("%d", &value);
    aTree = createNode (0, &value);

    do {
        menu(&choice);
        switch (choice) {

            case 1:
                printf("\nEnter the new child value: ");
                scanf("%d", &value);
                //NaryTree *aNode = createNode (0, value);
                appendChild(aTree, &value);
                break;

            case 2:
                //printf("%d", *aTree->data);
                printArrayTree(aTree);
                break;

            case 3:
                printf("\n\n***THE END***\n\n");
                break;
        }
    } while (choice > 0 && choice <= 2);

    system("PAUSE");

    return 0;
}

void menu(int *choice){
    printf("\n");
    printf("1. Insert new child\n");
    printf("2. Print NaryTree\n");
    printf("3. Exit");
    printf("\nEnter your choice: ");
    scanf("%d", &*choice);
}

All the code (except the main) is taken from here --> CLICK HERE

Every help or suggestion will be greatly appreciated. Thanks in advance :)


Solution

  • Your error is in the initialization of your Node: you don't alloc the memory buffer for the data. You make it point to your parameter, that is on the stack and not on the heap. As soon as your createNodefunction end, the stack is emptied and your parameter (so your data value) is lost.

    NaryTree *createNode ( int children , int *data) { 
        // Allocate space for a new NaryNode in memory
        NaryNode *node = (NaryNode*) calloc (1 , sizeof (NaryNode) );
    
        // Set the contents of the NaryNode appropriately
        // node->data = data; 
        node->data = malloc(sizeof(node->data));
        *node->data = *data;
        node->n = children ; 
        node->child = (NaryNode**) calloc ( children , sizeof (NaryNode*) );
    
        // Return the node we initialized
        return node;
    }
    

    Or, more simpler:

    typedef struct sNaryNode { 
         // int *data; // Point to the node ’s data
         int data; // contains the node ’s data
         int n; // The number of children 
         struct sNaryNode **child; // The child list
    } NaryNode;
    

    And pass to createNode the int data directly and not a pointer:

    NaryTree *createNode ( int children , int data) { 
        // Allocate space for a new NaryNode in memory
        NaryNode *node = (NaryNode*) calloc (1 , sizeof (NaryNode) );
    
        // Set the contents of the NaryNode appropriately
        // node->data = data; 
        node->n = children ; 
        node->child = (NaryNode**) calloc ( children , sizeof (NaryNode*) );
    
        // Return the node we initialized
        return node;
    }