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!

Some further findings...

Since it seems like the problem occurrs after parse, I conducted some experiments on the printf's that followed (in my main function).

If I make the order of printf's as:

Code:

---

        printf("What's the right son? %c\n", (&aNode)->RightSon->data);
        printf("What's the right son? %c\n", (&aNode)->RightSon->data);
        printf("What's the node data? %c\n", (&aNode)->data);

---

I get

Code:

---

What's the right son? G //which is correct
What's the right son? á //which is corrupted
What's the node data? A

---

If the order of printf's is left-left-node, I get L (which is correct), an ascii balderdash (which is corrupted) and A.

If right-left-son, I get G-ascii balderdash-A.

In any of the sequences I mentioned above, the printf inside toPrint displays the same ascii balderdash.

Familiar phenomenon?

This may or may not be related since you have so many self-defined functions like pop, push, queue class and so on (that you did not share). Anywho, look at this bit of code. If one of them is NULL, and other is not, you will not traverse that non-NULL child. Unless you are assuming this tree is always balanced.

Code:

---

// in the toPrint() function
if(holder->LeftSon != NULL && holder->RightSon != NULL){
    enqueue(&makeLevelOrder, holder->LeftSon);
    enqueue(&makeLevelOrder, holder->RightSon);
}

---

Also, in your toPrint() function you are not checking for NULL data, which should never happen, but it may help narrow things down.

Code:

---

                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");

---

pointLeftTo(&thisNode, &LNode);
pointRightTo(&thisNode, &RNode);
It seems to me like your tree consists of a bunch of pointers to local variables.

The variables go out of scope, and take all sense of sanity in your tree with it.

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!

Quote:

---

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?

---

Pointers.

Code:

---


struct myStruct
{
    int x;
};

myStruct* some_pointer_to_myStruct = new myStruct;

---

The some_pointer_to_myStruct variable is now available where ever it is being used/passed to. This should give you an idea on creating something that can be used where ever. In one part of your code you're dereferencing a pointer. Why not have the function take pointers, and not worry about local/global scope? You're also still passing a reference of a local variable 'NodeStack', if that really matters outside of the local scope or not, not sure. If not, then why is the function wanting a reference/pointer? Just some things to think about.

Great, so you replaced local variables with a memory leak.

There seems to be a logical inconsistency between your tree and your stack.
Sometimes you seem to be pushing pointers, and other times it's the value.

Past the code for say push() so we have an idea of what it is you actually do here.

And draw some diagrams on paper (boxes for memory, arrows for pointers) and sketch out the tree for your test case. Model what SHOULD happen on paper, then make the code do that.

Random hacking the code won't cut it.

Quote:

---

There seems to be a logical inconsistency between your tree and your stack.
Sometimes you seem to be pushing pointers, and other times it's the value.

---

Yep. I noticed eventually and solved. I settled for a stack of pointers.

(And also, the most recent code I posted is a big mistake, I realized. The codes in my first post get more things done [albeit chaotically, incorrectly])

Anyway, I resolved it though this: I malloced inside the conditional clauses instead of outside (scwizzo's post led me to this). That way, on every iteration, new memory gets allocated without damaging what is already in the stack.

Code:

---

while(i < datalen){
                        if(tag[i] == '0'){
                                BTNode *holderNode;
                                holderNode = (BTNode *) malloc(sizeof(BTNode));
                               
                                holderNode->data = data[i];
                                holderNode->LeftSon = NULL;
                                holderNode->RightSon = NULL;
                               
                                push(&NodeStack, holderNode);
                        }
                        else if(tag[i] == ' '){
                        }
                        else{
                                BTNode *holderNode;
                                holderNode = (BTNode *) malloc(sizeof(BTNode));
                               
                                BTNode *holderLeft;
                                holderLeft = (BTNode *) malloc(sizeof(BTNode));
                               
                                BTNode *holderRight;
                                holderRight = (BTNode *) malloc(sizeof(BTNode));
                               
                                holderNode->data = data[i];
                               
                                pop(&NodeStack, &holderRight);
                                pop(&NodeStack, &holderLeft);
                               
                                holderNode->LeftSon = holderLeft;
                                holderNode->RightSon = holderRight;
                               
                                push(&NodeStack, holderNode);
                        }
                       
                        i++;
                }

---

Thanks much! (--,)