Thread: Binary Tree gets corrupted. Confusing...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    20

    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!

  2. #2
    Registered User
    Join Date
    Nov 2009
    Posts
    20
    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?

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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");

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    20

    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!

  6. #6
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Registered User
    Join Date
    Nov 2009
    Posts
    20

    Solved!

    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! (--,)
    Last edited by skytreader; 02-19-2010 at 12:05 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM