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!