Binary Tree in C Insertion Error

Question

I'm quite new to C and I'm trying to implement a Binary Tree in C which will store a number and a string and then print them off e.g.

1 : Bread

2 : WashingUpLiquid

etc.

The code I have so far is:

#include <stdio.h>
#include <stdlib.h>
#define LENGTH 300

struct node {
 int data;
 char * definition;
 struct node *left;
 struct node *right;
};


struct node *node_insert(struct node *p, int value, char * word);

void print_preorder(struct node *p);

int main(void) {
 int i = 0;
 int d = 0;
 char def[LENGTH];
 struct node *root = NULL; 

 for(i = 0; i < 2; i++)
 {
 printf("Please enter a number: \n");
 scanf("%d", &d);
 printf("Please enter a definition for this word:\n");
 scanf("%s", def);
 root = node_insert(root, d, def);
 printf("%s\n", def);
 }

 printf("preorder : ");
 print_preorder(root);
 printf("\n");

 return 0;
}
struct node *node_insert(struct node *p, int value, char * word) {
 struct node *tmp_one = NULL;
 struct node *tmp_two = NULL;

 if(p == NULL) {
  p = (struct node *)malloc(sizeof(struct node));
  p->data = value;
  p->definition = word;
  p->left = p->right = NULL;
 } else {
  tmp_one = p;
  while(tmp_one != NULL) {
   tmp_two = tmp_one;
   if(tmp_one->data > value)
    tmp_one = tmp_one->left;
   else
    tmp_one = tmp_one->right;
  }

  if(tmp_two->data > value) {
   tmp_two->left = (struct node *)malloc(sizeof(struct node));
   tmp_two = tmp_two->left;
   tmp_two->data = value;
   tmp_two->definition = word;
   tmp_two->left = tmp_two->right = NULL;
  } else {
   tmp_two->right = (struct node *)malloc(sizeof(struct node)); 
   tmp_two = tmp_two->right;
   tmp_two->data = value;
   tmp_two->definition = word;
   tmp_two->left = tmp_two->right = NULL;
  }
 }

 return(p);
}

void print_preorder(struct node *p) {
 if(p != NULL) {
  printf("%d : %s\n", p->data, p->definition);
  print_preorder(p->left);
  print_preorder(p->right);
 }
}

At the moment it seems to work for the ints but the description part only prints out for the last one entered. I assume it has something to do with pointers on the char array but I had no luck getting it to work. Any ideas or advice?

Thanks

Answer 1

You're always doing a scanf into def and then passing that to your insert routine which just saves the pointer to def. So, since all of your entries point to the def buffer, they all point to whatever was the last string you stored in that buffer.

You need to copy your string and place a pointer to the copy into the binary tree node.

Answer 2

The problem is that you're using the same buffer for the string. Notice your struct is holding a pointer to a char, and you are passing the same char array as that pointer each time.

When you call scanf on the buffer, you are changing the data it points to, not the pointer itself.

To fix this, before assigning it over to a struct, you can use strdup. So the lines of code would become

tmp_*->definition = strdup(word);

Keep in mind that the char array returned by strdup must be freed once you are done with it, otherwise you'll have a leak.