Binary Tree gets corrupted. Confusing...
Hi all. I'm creating binary trees from some given data. Afterwards, I need to traverse it in level order. However, my binary tree seems to get corrupted as my code moves on from line to line.
Being called at main():
Code:
main(){
/*Don't mind the first block for now*/
BTNode aNode;
InitBTNode(&aNode, 'f');
char algorithm_word[] = "ORLHMITGA";
char algorithm_tag[] = "001001011";
parse(algorithm_word, algorithm_tag, &aNode);
printf("What's the left son? %c\n", (&aNode)->LeftSon->data);
printf("What's the node data? %c\n", (&aNode)->data);
printf("What's the right son? %c\n", (&aNode)->RightSon->data);
toPrint(&aNode);
}
And then, my parse function, which generates the binary tree
Code:
void parse(char data[], char tag[], BTNode *finishedBT){
stack NodeStack;
InitStack(&NodeStack);
int datalen = strlen(data);
int taglen = strlen(tag);
if(datalen == taglen && isValid(tag)){
int i = 0;
while(i < taglen){
BTNode thisNode;
InitBTNode(&thisNode, data[i]);
if(tag[i] == '0'){
push(&NodeStack, thisNode);
printf("Pushed a node with data %c\n", (&thisNode)->data);
}
else{
BTNode RNode;
pop(&NodeStack, &RNode);
BTNode LNode;
pop(&NodeStack, &LNode);
pointLeftTo(&thisNode, &LNode);
pointRightTo(&thisNode, &RNode);
printf("=======\n");
printf("Let's look at the node we are pushing...\n");
printf("Left son data: %c\n", (&thisNode)->LeftSon->data);
printf("Node data: %c\n", (&thisNode)->data);
printf("Right son data: %c\n", (&thisNode)->RightSon->data);
printf("=======\n");
push(&NodeStack, thisNode);
printf("Again, to check...\n");
printf("Left son data: %c\n", (&thisNode)->LeftSon->data);
printf("Node data: %c\n", (&thisNode)->data);
printf("Right son data: %c\n", (&thisNode)->RightSon->data);
}
i++;
}
pop(&NodeStack, finishedBT);
}
else{
ValidTagSeq = FALSE;
}
}
(Note: The given sequence is the postorder sequence. The tag argument, specifies if the node with the corresponding data is an internal node or a leaf. We assume strictly binary trees.)
I am satisfied with my parse function. I only showed it here to make a point on the printf's (later). Next, my toPrint function, which traverses the generated binary tree in level order and creates a table from it.
Code:
void toPrint(BTNode *BinaryTree){
printf("From toPrint: What is the LeftSon now? %c\n", BinaryTree->LeftSon->data);
queue makeLevelOrder;
InitQueue(&makeLevelOrder);
enqueue(&makeLevelOrder, BinaryTree);
printf("+=====================+\n");
printf("| LSON NODE RSON |\n");
printf("|=====================|\n");
while(!isEmpty(&makeLevelOrder)){
BTNode *holder;
holder = (BTNode *) malloc(sizeof(BTNode));
dequeue(&makeLevelOrder, holder);
if(holder->LeftSon == NULL){
printf("| ");
}
else{
printf("| %c", holder->LeftSon->data);
}
printf(" %c", holder->data);
if(holder->RightSon == NULL){
printf(" ");
}
else{
printf(" %c", holder->RightSon->data);
}
printf(" |\n");
if(holder->LeftSon != NULL && holder->RightSon != NULL){
enqueue(&makeLevelOrder, holder->LeftSon);
enqueue(&makeLevelOrder, holder->RightSon);
}
}
}
Here is where things go wrong. From the last few messages generated by the printf's,
Code:
=======
Let's look at the node we are pushing...
Left son data: L
Node data: A
Right son data: G
=======
Again, to check...
Left son data: L
Node data: A
Right son data: G
What's the left son? L
What's the node data? A
What's the right son? á
From toPrint: What is the LeftSon now? ¦
+=====================+
| LSON NODE RSON |
|=====================|
| G A á |
As you see, by the time it is accessed by main(), the right son is corrupted. Upon entry to toPrint, LeftSon is also corrupted. Then when generating the table, LeftSon becomes G and RightSon is plain corrupted. Also, the program terminates prematurely, with Windows saying that it performed an illegal operation. Any insights?
Thanks!
Hopefully, a little less confusing now
Salem. I think I get what you mean. In the next iteration, the contents of my local variables change and the contents of my stack as well. Hence, it goes well in the printf's but not afterwards.
To this end, I have revised my code:
Code:
BTNode *holderNode;
holderNode = (BTNode *) malloc(sizeof(BTNode));
BTNode *holderLeft;
holderLeft = (BTNode *) malloc(sizeof(BTNode));
BTNode *holderRight;
holderRight = (BTNode *) malloc(sizeof(BTNode));
void parse(char data[], char tag[], BTNode *finishedBT){
stack NodeStack;
InitStack(&NodeStack);
int datalen = strlen(data);
int taglen = strlen(tag);
if(datalen == taglen && isValid(tag)){
int i = 0;
BTNode *holderNode;
holderNode = (BTNode *) malloc(sizeof(BTNode));
BTNode *holderLeft;
holderLeft = (BTNode *) malloc(sizeof(BTNode));
BTNode *holderRight;
holderRight = (BTNode *) malloc(sizeof(BTNode));
while(i < datalen){
if(tag[i] == 0){
holderNode->data = data[i];
holderNode->LeftSon = NULL;
holderNode->RightSon = NULL;
push(&NodeStack, *holderNode);
}
else{
holderNode->data = data[i];
pop(&NodeStack, holderRight);
pop(&NodeStack, holderLeft);
holderNode->LeftSon = holderLeft;
holderNode->LeftSon = holderRight;
}
free(holderNode);
free(holderLeft);
free(holderRight);
holderNode = (BTNode *) malloc(sizeof(BTNode));
holderLeft = (BTNode *) malloc(sizeof(BTNode));
holderRight = (BTNode *) malloc(sizeof(BTNode));
i++;
}
}
else{
ValidTagSeq = FALSE;
}
}
Holder nodes are now global. However, I encounter the following error upon compile
Code:
202: error: conflicting types for 'holderNode'
201: error: previous declaration of 'holderNode' was here
202: warning: initialization makes integer from pointer without a cast
202: error: initializer element is not constant
202: warning: data definition has no type or storage class
and so on for the other two variables (holderLeft and holderRight).
So I change them again to
Code:
void parse(char data[], char tag[], BTNode *finishedBT){
stack NodeStack;
InitStack(&NodeStack);
int datalen = strlen(data);
int taglen = strlen(tag);
if(datalen == taglen && isValid(tag)){
int i = 0;
BTNode *holderNode;
holderNode = (BTNode *) malloc(sizeof(BTNode));
BTNode *holderLeft;
holderLeft = (BTNode *) malloc(sizeof(BTNode));
BTNode *holderRight;
holderRight = (BTNode *) malloc(sizeof(BTNode));
while(i < datalen){
if(tag[i] == 0){
holderNode->data = data[i];
holderNode->LeftSon = NULL;
holderNode->RightSon = NULL;
push(&NodeStack, *holderNode);
}
else{
holderNode->data = data[i];
pop(&NodeStack, holderRight);
pop(&NodeStack, holderLeft);
holderNode->LeftSon = holderLeft;
holderNode->LeftSon = holderRight;
}
free(holderNode);
free(holderLeft);
free(holderRight);
holderNode = (BTNode *) malloc(sizeof(BTNode));
holderLeft = (BTNode *) malloc(sizeof(BTNode));
holderRight = (BTNode *) malloc(sizeof(BTNode));
i++;
}
}
else{
ValidTagSeq = FALSE;
}
}
However, this makes my stack underflow, which I guess is because I freed the holder variables, and hence destroyed the contents of my stack.
My new question: How do I use self-defined structures in loops such that they have long-lasting effects, and can be seen by other functions?
Thanks!