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 :)
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 createNode
function 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;
}