Moving a binary tree in C

Question

I am trying to cross a binary tree in C. My tree contains an AST node (abstract syntax node tree for the compiler). ASTnode reserves a nodetype that specifies the given node type (for example, INT OP or CHAR and TYPE, we do not need to relate to other types), the rest of the members are pointers left and right, and finally we save.

Here is the code to move:

void traverse(struct ASTNode *root) { if(root->nodeType == OP){ printf("OP \n"); if(root->left != NULL){ printf("left - "); traverse(root->left); } if(root->right != NULL){ printf("right - "); traverse(root->right); } return; } else{ if(root != NULL && root->nodeType == INT) { printf("INT - "); printf("INT: %d\n",root->value); } if(root != NULL && root->nodeType == CHAR) { printf("CHAR - "); printf("CHAR: %c\n",root->chValue); } return; } } 

Also, we cannot assign left or right CONSTANT values ​​to nodes, because in AST, constant values ​​do not contain any additional values.

Updated:

The problem is my main call:

  int main() { struct ASTNode *node1 = makeCharNode('a'); struct ASTNode *node2 = makeCharNode('b'); struct ASTNode *node10 = makeCharNode('c'); struct ASTNode *node3 = makeINTNode(19); struct decl *d = (struct decl*) malloc(sizeof(struct decl*)); struct decl *d2 = (struct decl*) malloc(sizeof(struct decl*)); struct ASTNode *node4 = makeNode(3,d,node3,node2); struct ASTNode *node5 = makeNode(3,d2,node4,node1); !! traverse(node4); } 

If we remove node5 (which is marked with the symbol !!), the code works very well, otherwise it will give a segmentation error.

Functions that work on makenode :

  struct ASTNode *makeNode(int opType,struct decl *resultType,struct ASTNode *left,struct ASTNode *right) { struct ASTNode *node= (struct ASTNode *) malloc(sizeof(struct ASTNode *)); node->nodeType = opType; node->resultType = resultType; node->left = left; node->right = right; return node; } struct ASTNode *makeINTNode(int value) { struct ASTNode *intnode= (struct ASTNode *) malloc(sizeof(struct ASTNode *)); intnode->nodeType = INT; intnode->value = value; return intnode; } struct ASTNode *makeCharNode(char chValue) { struct ASTNode *charNode = (struct ASTNode *) malloc(sizeof(struct ASTNode *)); charNode->nodeType = CHAR; charNode->chValue = chValue; return charNode; } 

Answer 1

Your wrong cards

  struct decl *d = (struct decl*) malloc(sizeof(struct decl*)); struct decl *d2 = (struct decl*) malloc(sizeof(struct decl*)); 

should be

  struct decl *d = (struct decl*) malloc(sizeof(struct decl)); struct decl *d2 = (struct decl*) malloc(sizeof(struct decl)); 

(or use sizeof * d instead of sizeof (struct decl)). In C, you do not need to specify the return value of malloc, btw.

Also, before accessing them, make sure that you set the items to NULL or another default value. malloc will not set them to 0 / NULL.

Answer 2

All that I see, maybe you want to check root->value et al before going to printf.

Also, although this should not cause errors, you might want to change

if(root != NULL && root->nodeType == CHAR)

to

else if(root != NULL && root->nodeType == CHAR)

Edit: wait, is there something here - when you go through root->left to go through, is that the same value or pointer? The function expects a pointer.

Answer 3

You do not check if "root" is NULL in your first if block. I think the easiest thing is to wrap

 if(root != NULL) 

around everything (except for the final return) and get rid of individual root! = NULL checks when printing the INT and CHAR nodes.

Share and enjoy.

EDIT: here is what I mean:

 void traverse(struct ASTNode *root) { if(root != NULL) { switch(root->nodeType) { case OP: printf("OP \n"); if(root->left != NULL) { printf("left - "); traverse(root->left); } if(root->right != NULL) { printf("right - "); traverse(root->right); } break; case INT: printf("INT - "); printf("INT: %d\n",root->value); break; case CHAR: printf("CHAR - "); printf("CHAR: %c\n",root->chValue); } } } 

The use of the switch instead of the if group has also changed.

I apologize for any syntax errors: this is not in my head, without a compiler.

Answer 4

The makeNode function must initialize all members of the structure. Perhaps this does not mean that one of the left / right pointers is NULL? Calling malloc () does not empty memory.

Ack - I'm blind. Nos answer is correct. Incorrect call to malloc. I was just adding noise.

Answer 5

Your code will be segfault on the first NULL node passed to traverse ().

You took care to check root != NULL inside your else block, but by then you have already dereferenced it. If you try to dereference a NULL pointer, you will be segfault.

Try to add

 if (!root) return; 

as your first line.

Answer 6

You are showing code highlighting the ' struct decl ' struct decl ; you do not show the code initializing them. It is not clear why makeNode () initializes its second argument or how it will do it. It is also unclear what 3 means. It is also not clear how " struct decl " integrates into ASTnode.

You can simplify traverse () by addressing exceptional cases earlier:

 void traverse(struct ASTNode *root) { if (root == NULL) // Or: assert(root != NULL); return; if (root->nodeType == OP) { printf("OP \n"); if (root->left != NULL) { printf("left - "); traverse(root->left); } if (root->right != NULL) { printf("right - "); traverse(root->right); } } else if (root->nodeType == INT) { printf("INT - "); printf("INT: %d\n", root->value); } else if (root->nodeType == CHAR) { printf("CHAR - "); printf("CHAR: %c\n", root->chValue); } else assert("Unrecognized nodeType" == 0); } 

This also applies to the impossible case - the unrecognized type of node. It also does not crash or burn if a null pointer is passed.

However, this still does not explain why your code crashes and does not crash depending on the optional ASTnode ... I am not sure that we have enough code to be sure why this is happening. Have you tried moving all the nodes (node1, node2, node3, node10)? This should be fine if the makeCharNode () and makeINTNode () functions work fine, but such rudimentary checks can save your bacon. It may be useful to see what the makeNode () function does; ensures that all parts of the node are properly initialized.