Thread: problem in storing data in a binary search tree

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    10

    problem in storing data in a binary search tree

    hi all,
    i want to read strings from a file and store them in a binary search tree. i can print the strings to the screen, but when i try to store them in the tree, only last string is stored in the root of the tree, others vanish. code is below

    Code:
    #include <stdio.h>
    //#include <iostream.h>
    #include <string.h>
    #include <malloc.h>
    //#include <string> --cpp only
    
    typedef struct BinaryNode
    {
    	char* data;
    	struct BinaryNode* left;
    	struct BinaryNode* right;
    
    }nodeType;
    
    nodeType* root = NULL;
     
    void insertToTree(char*);
    
    nodeType* insertToNode(char*, nodeType*);
    
    int isEmpty();
    
    void printTree();
    
    void printNode(nodeType*);
    
    int main()
    {
    	
    	FILE* inputFile = fopen("deneme.txt", "r");	
    	
    	char* lino;
    
    	while( !feof(inputFile)){	
    		
    		char line[10];
    		lino = (char*)malloc(sizeof(char));
    		lino = fgets(line, sizeof(line), inputFile); 
    		insertToTree( lino  );
    		printf(lino);
    	}
    	printf("\n");	
    	printf("printing whole tree \n");
    	printTree();
    	fclose(inputFile);
    	
                    return 0;	
    }
    
    void insertToTree(char* x)
    {	
    	root = insertToNode(x, root);
    }
    
    nodeType* insertToNode(char* x, nodeType* t){
    	
    	if (t == NULL) {
    		
    		t = ( nodeType * )malloc(sizeof( nodeType ) );		
    		t->data = x;
    		t->left = NULL;
    		t->right = NULL; 
    		
    	}
    
    	else if(strcmp(x, t->data) < 0){
    		
    		t->left = insertToNode(x, t->left);
    
    	}
    
    	else if(strcmp(x, t->data) > 0){
    
    		t->right = insertToNode(x, t->right);
    
    	}
    
    	else
    		;
    	
    	return t;
    }
    
    void printTree(){
    	
    	if( isEmpty( ) != 0)
    		printf( "Empty tree\n" );
        else
            printNode( root );	
    }
    
    int isEmpty( )
    {
    	int TRUE = 5;
    	int FALSE = 0;
    	
    	if (root == NULL)
    		return TRUE;
    	else 
    		return FALSE;
    }
    
    void printNode( nodeType* t )
    {
    	if( t != NULL )
        {
    		printNode( t->left );
            printf("data: %s\n", t->data );
            printNode( t->right );
    	}
    }

  2. #2
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    Well, I get the unhandled exception here:
    Code:
    else if(strcmp(x, t->data) < 0){
    To me that means either x or t->data are NULL and trying to be accessed. and since you check t, and you never check the return from malloc or fgets for NULL I would be willing to wager that your problem lies in here:
    Code:
    while( !feof(inputFile)){    
            
            char line[10];
            lino = (char*)malloc(sizeof(char));
            lino = fgets(line, sizeof(line), inputFile); 
            insertToTree( lino  );
            printf(lino);
        }
    Unless you are using a C++ compiler you should never cast malloc(). This is why.

    This is a better read loop:
    Code:
    lino = (char*)malloc(sizeof(line));
    
    while((lino = fgets(line, sizeof(line), inputFile))){    
         insertToTree( lino  );
         printf(lino);
    }
    Also when you add your node you never initialize your data variable or allocate any space for it. You add node should look like:
    Code:
    t->data = (char*)malloc(sizeof(*x));
    if(t->data != NULL)
         strcpy(t->data,x);
    This will now print out the tree.
    Last edited by andyhunter; 02-12-2005 at 08:46 AM.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  3. #3
    Registered User
    Join Date
    Feb 2005
    Posts
    10
    thanks a lot andy, it works very well

  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
    Code:
    #include <stdio.h>
    //#include <iostream.h>
    #include <string.h>
    #include <malloc.h>
    //#include <string> --cpp only
    Please make up your mind as to whether you're compiling C or C++.
    If it's C, then you need to
    a) stop casting malloc
    b) #include <stdlib.h>
    There is no standard header called malloc.h

    Code:
    lino = (char*)malloc(sizeof(line));
    
    while((lino = fgets(line, sizeof(line), inputFile))){
    This is just a memory leak - there is no need to allocate anything to lino
    In fact, it's a useless variable, since you may as well just write
    Code:
    while( fgets(line, sizeof(line), inputFile) ) {    
         insertToTree(line);
         printf(line);
    }

    >
    Code:
    int isEmpty( )
    {
        int TRUE = 5;
        int FALSE = 0;
        
        if (root == NULL)
            return TRUE;
        else 
            return FALSE;
    }
    What an utterly bizarre value for true - most people (and the language) use the value 1.
    This function can be reduced to
    Code:
    int isEmpty( )
    {
        return root == NULL;
    }
    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
    Feb 2005
    Posts
    10
    well i started programming in c very recently, after programming in java for sometime. anyway thx for your help, below is the last version of my code
    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    typedef struct BinaryNode
    {
    	char* data;
    	struct BinaryNode* left;
    	struct BinaryNode* right;
    
    }nodeType;
    
    nodeType* root = NULL;
     
    void insertToTree(char*);
    
    nodeType* insertToNode(char*, nodeType*);
    
    int isEmpty();
    
    void printTree();
    
    void printNode(nodeType*);
    
    int main(int argc, char* argv[])
    {
    	//char* fileName = argv[1];
    	char* fileName = "deneme.txt";
    	
    	FILE* inputFile = fopen(fileName, "r");
    			
    	char line[1000];	
    		
    	while( fgets(line, sizeof(line), inputFile) ){
    		
    		insertToTree( line  );
    		printf(line);
    	}
    	printf("\n");	
    	printf("printing whole tree \n");
    	printTree();
    	fclose(inputFile);
    	
    	return 0;	
    }
    
    void insertToTree(char* x)
    {	
    	root = insertToNode(x, root);
    }
    
    nodeType* insertToNode(char* x, nodeType* t){
    	
    	if (t == NULL) {		
    		
    		t = malloc(sizeof (nodeType) );
    		t->data = malloc(sizeof(*x));
    		
    		//if(t->data != NULL)
    		strcpy(t->data,x);
    		
    		t->left = NULL;
    		t->right = NULL; 
    		
    	}
    
    	else if(strcmp(x, t->data) < 0){
    		
    		t->left = insertToNode(x, t->left);
    
    	}
    
    	else if(strcmp(x, t->data) > 0){
    
    		t->right = insertToNode(x, t->right);
    
    	}
    
    	else
    		;
    	
    	return t;
    }
    
    void printTree(){
    	
    	if( isEmpty( ) )
    		printf( "Empty tree\n" );
        else
            printNode( root );	
    }
    
    int isEmpty( )
    {
    	
    	return root == NULL;
    }
    
    void printNode( nodeType* t )
    {
    	if( t != NULL )
        {
    		printNode( t->left );
            printf("data: %s\n", t->data );
            printNode( t->right );
    	}
    }

  6. #6
    Registered User
    Join Date
    Feb 2005
    Posts
    10
    i checked the code with valgrind (1.9.6) and it gives these errors

    Invalid write of size 1
    ==2143== at 0x4015FBE9: strcpy (in /usr/lib/valgrind/valgrind.so)
    ==2143== by 0x804864D: insertToNode (in /home/edip/Documents/cs342-os/hw1.exe)
    ==2143== by 0x8048604: insertToTree (in /home/edip/Documents/cs342-os/hw1.exe)
    ==2143== by 0x8048581: main (in /home/edip/Documents/cs342-os/hw1.exe)
    ==2143== Address 0x40F30201 is 0 bytes after a block of size 1 alloc'd
    ==2143== at 0x4015F3AF: malloc (in /usr/lib/valgrind/valgrind.so)
    ==2143== by 0x8048638: insertToNode (in /home/edip/Documents/cs342-os/hw1.exe)
    ==2143== by 0x8048604: insertToTree (in /home/edip/Documents/cs342-os/hw1.exe)
    ==2143== by 0x8048581: main (in /home/edip/Documents/cs342-os/hw1.exe)

    error summary and leak summary is

    ERROR SUMMARY: 299 errors from 24 contexts (suppressed: 0 from 0)
    ==2143== malloc/free: in use at exit: 323 bytes in 38 blocks.
    ==2143== malloc/free: 39 allocs, 1 frees, 687 bytes allocated.
    ==2143== For counts of detected errors, rerun with: -v
    ==2143== searching for pointers to 38 not-freed blocks.
    ==2143== checked 3364000 bytes.
    ==2143==
    ==2143== LEAK SUMMARY:
    ==2143== definitely lost: 0 bytes in 0 blocks.
    ==2143== possibly lost: 0 bytes in 0 blocks.
    ==2143== still reachable: 323 bytes in 38 blocks.
    ==2143== suppressed: 0 bytes in 0 blocks.
    Last edited by alavardi; 02-13-2005 at 03:22 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Binary Search Tree
    By dookie in forum C++ Programming
    Replies: 5
    Last Post: 05-10-2008, 04:35 PM
  2. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  3. Binary Search Tree scope? problem
    By tms43 in forum C++ Programming
    Replies: 5
    Last Post: 11-01-2006, 10:13 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM