1

Here's some code in C. Basically, It create a small binary tree and then traverse it in pre-order recursively. While I expect '1 2 3', it keeps give me 'printf' result '0 0 3'.

Does anybody have any idea about the code below?

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

typedef struct binary_tree{
  struct binary_tree *left;
  struct binary_tree *right;
  int value;
}binary_tree;

void init_btree(binary_tree *root);

// traverse the tree in pre-order recursively
void pre_order_r(const binary_tree *root){
  if(root == NULL){
    return;
  }
  printf("%d ", root->value);
  pre_order_r(root->left);
  pre_order_r(root->right);
}

int main() {
  binary_tree *root = (binary_tree*)malloc(sizeof(binary_tree*));;
  init_btree(root);
  pre_order_r(root);
  printf("\n");
}

void init_btree(binary_tree *root){
  root->left = root->right = NULL;
  root->value = 1;
  binary_tree * p1 = (binary_tree*)malloc(sizeof(binary_tree*));
  p1->left = p1->right = NULL;
  p1->value = 2;
  binary_tree * p2 = (binary_tree*)malloc(sizeof(binary_tree*));
  p2->left = p2->right = NULL;
  p2->value = 3;

  root->left = p1;
  root->right = p2;
}
Yu Hao
  • 119,891
  • 44
  • 235
  • 294
beanmoon
  • 59
  • 2
  • 8

2 Answers2

3

Change

(binary_tree*) malloc(sizeof(binary_tree*))

to

malloc(sizeof(binary_tree))

You want memory for this struct, not memory for a pointer for this struct.

And don't cast the value of malloc. This is needed in C++, but you are programming in C where an implicit conversion is doing this for you.

LMF
  • 463
  • 2
  • 10
2

I think, your problem is 

binary_tree *root = (binary_tree*)malloc(sizeof(binary_tree*));

root is a pointer to binary_tree type. So, you need to allocate memory for the binary_tree structure, not a "pointer-to-structure".

If you want a clearer picture, you can print the sizes of both binary_tree and *binary_tree using sizeof().

You can re-write that allocation statement in a robust way as

 binary_tree *root = malloc(sizeof*root);

Some general advices:

  1. Always check for the success of malloc() before using the returned pointer.
  2. Please see why not to cast the return value of malloc() and family in C.
  3. The recommended signature of main() is int main(void).
Community
  • 1
  • 1
Sourav Ghosh
  • 133,132
  • 16
  • 183
  • 261