Help with Binary Search Tree insertion

This is a discussion on Help with Binary Search Tree insertion within the C++ Programming forums, part of the General Programming Boards category; The purpose of it is to grab a word from a text file, (text1.txt), and then organize the word into ...

  1. #1
    Shake Zula- The Mic Rula!
    Join Date
    Sep 2004
    Posts
    69

    Help with Binary Search Tree insertion

    The purpose of it is to grab a word from a text file, (text1.txt), and then organize the word into a BST, then grab another word, put it in the appropriate node on the BST, and repeat until EOF is reached in text1.txt.... here's the code i have so far...
    Code:
    #include <iostream.h>
    #include <math.h>
    #include <stdlib.h>
    #include <fstream.h>
    #include <string.h>
    
    struct node 
    {
    
    	char wordFromFile [20];
    	node *left;
    	node *right;
    
    	treeNodeNew(char newWord[]);
    
    };
    
    struct node* allNode (char data[20])
    {
    	struct node* node = new(struct node);
    	node->wordFromFile[20] = data[20];
    	node->left = NULL;
    	node->right = NULL;
    
    	return (node);
    };
    
    
    
    struct node* insert(struct node* node, char data[20]) 
    {
      if (node == NULL) 
      {
        return(allNode(data));
      }
      else 
      {
      
        if (data <= node->wordFromFile) 
    		node->left = insert(node->left, data);
        else 
    		node->right = insert(node->right, data);
    
        return(node); 
      }
    } 
    
    
    
    int lookup(struct node* node, int target);
    
    
    
    
    
    int main()
    
    {
    
    	node newNode;
    	char word [20];
    	
    	ifstream inFile1 ("text1.txt");
    	if (!inFile1)
    	{
    		cout<<"Error opening file!"<<endl;
    		exit (1);
    	}
    	
    	while (!inFile1.eof())
    	{
    	
    		inFile1>>word;
    		strcpy (newNode.wordFromFile, word);
    		
    	}
    	
    
    
    inFile1.close();
    
    
    
    return 0;
    }
    
    
    int lookup(struct node* allNode, char target[20])
    {
    	if (allNode == NULL)
    		return (false);
    	else
    	{
    		if (target == allNode->wordFromFile)
    			return (true);
    	else
    	{
    		if (target < allNode->wordFromFile)
    			return (lookup(allNode->left, target));
    		else
    			return (lookup(allNode->right, target));
    	}
    	}
    }

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,793
    Code:
    #include <iostream.h>
    #include <math.h>
    #include <stdlib.h>
    #include <fstream.h>
    #include <string.h>
    You should be using the newer headers as follows:

    Code:
    #include <iostream>
    #include <cmath>
    #include <cstdlib>
    #include <fstream>
    #include <cstring>
    using namespace std;
    Code:
    struct node 
    {
        char wordFromFile [20];
        node *left;
        node *right;
    
        treeNodeNew(char newWord[]);
    
    };
    What is the purpose of treeNodeNew? Is it meant to be a constructor of some sort? Where is the implementation?

    Code:
    struct node* allNode (char data[20])
    {
        struct node* node = new(struct node);
        node->wordFromFile[20] = data[20];
        node->left = NULL;
        node->right = NULL;
    
        return (node);
    };
    The line above in red is problematic. You need to use strcpy here. I.e. strcpy(node->wordFromFile,data) or better yet make use of a string container instead of a character array.

    Code:
    struct node* insert(struct node* node, char data[20]) 
    {
        if (node == NULL) 
        {
            return(allNode(data));
        }
        else 
        {
      
            if (data <= node->wordFromFile) 
                node->left = insert(node->left, data);
            else 
                node->right = insert(node->right, data);
    
            return(node); 
        }
    }
    You can't compare character arrays this way, you can with string containers but not character arrays. If using character arrays, you must use the strcmp function.

    Code:
    int lookup(struct node* node, int target);
    
    
    int main()
    {
        node newNode;
        char word [20];
    	
        ifstream inFile1 ("text1.txt");
        if (!inFile1)
        {
            cout<<"Error opening file!"<<endl;
            exit (1);
        }
    	
        while (!inFile1.eof())
        {
            inFile1>>word;
            strcpy (newNode.wordFromFile, word);
        }
    	
        inFile1.close();
    
        return 0;
    }
    Instead of declaring a node instance newNode, you should declare a pointer and initialize it to NULL. Also, you don't want to use eof as a test condition in your while loop. A better way would likely be while( inFile1 >> word ) followed by your call to the insert function within the body of the loop.

    Code:
    int lookup(struct node* allNode, char target[20])
    {
        if (allNode == NULL)
            return (false);
        else
        {
            if (target == allNode->wordFromFile)
                return (true);
            else
            {
                if (target < allNode->wordFromFile)
                    return (lookup(allNode->left, target));
                else
                    return (lookup(allNode->right, target));
            }
        }
    }
    Again, using character arrays you cannot test for equality/less-than using the == and < operators like you could if you were using string objects. You must use strcmp here instead.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Shake Zula- The Mic Rula!
    Join Date
    Sep 2004
    Posts
    69
    i'm not sure what you mean when you say "declare a pointer and initialize it to NULL", i'm not real sure how to do that. also, i'm not sure how to take the word from the file, and pass it into the node, i'm really lost, in case you can't tell...

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    Using trees is an exaggeration of using lists in terms of making nodes, attaching/detaching them, etc. If you are familiar with creating your own lists, etc. then the techniques used there should be readily transferable to treees.

    Here's a review for using pointers to hold strings and obtaining data from file to place into strings. Assuming infile is an ifstream associated with a file that has appropriate data in it and MAX is a const int of whatever size you need declared someplace appropriate, then:

    Code:
    //example of getting C style string from file and putting it in a pointer.
     
    //declare ponter and assign memory to it
    char * name = new char[MAX + 1];
    infile >> name;  //or use another istream method if desired
    delete name;
     
    //now the pointer is embedded in a struct as a member variable.  This would be similar to a node you could use in a list or a tree.
     
    struct person
    {
       //pointer member variable
       char * name;
     
       //constructor declaring memory for pointer
       person () { name = new char[MAX + 1]};
     
       //destructor to release memory for pointer
       ~person {delete name;}
    }
     
    person * pal = new person;
    infile >> pal->name;
    You're only born perfect.

  5. #5
    Shake Zula- The Mic Rula!
    Join Date
    Sep 2004
    Posts
    69
    that really didn't help me out too much, i'm still confused, maybe even worse now... all i'm really troubled with is how to get the word from the file into a new node, then i need to search the tree with the new node i've created with the word from the file, and then if it's not in there, place it in the proper place.

    I'm also a little confused of how to call "insert" within main.
    Code:
    int main()
    {
        node newNode;
        char word [20];
    	
        ifstream inFile1 ("text1.txt");
        if (!inFile1)
        {
            cout<<"Error opening file!"<<endl;
            exit (1);
        }
    	
        while (!inFile1.eof())
        {
            inFile1>>word;
            strcpy (newNode.wordFromFile, word);
    
            // need to call "insert" here and have the word from the file inserted into a new node
    
        }
    	
        inFile1.close();
    
        return 0;
    }

  6. #6
    Shake Zula- The Mic Rula!
    Join Date
    Sep 2004
    Posts
    69
    heres the revised code after making the "strcmp" changes and that's it, still need alot of help and still real confused

    Code:
    #include <iostream.h>
    #include <math.h>
    #include <stdlib.h>
    #include <fstream.h>
    #include <string>
    
    
    struct node 
    {
    
    public:
    	char wordFromFile [20];
    	node *left;
    	node *right;
    
    
    
    };
    
    struct node* allNode (char data[20])
    {
    	struct node* node = new (struct node);
    	strcpy(node->wordFromFile, data);
    	node->left = NULL;
    	node->right = NULL;
    
    	return (node);
    };
    
    struct node* insert (struct node* node, char data[20])
    {
    	if (node == NULL)
    	{	
    		return (allNode(data));
    	}
    	else 
    	{
    		if (strcmp(data, node->wordFromFile)<1)
    			node->left = insert (node->left, data);
    	
    		else
    			node->right = insert (node->right, data);
    		return (node);
    	}
    }
    
    
    int lookup(struct node* node, int target);
    
    
    
    int main()
    
    {
    
    	node newNode;
    	char word [20];
    
    	int n = 1;
    	
    	ifstream inFile1 ("text1.txt");
    	if (!inFile1)
    	{
    		cout<<"Error opening file!"<<endl;
    		exit (1);
    	}
    	
    	while (!inFile1.eof())
    	{
    	
    		inFile1>>word;
    		strcpy (newNode.wordFromFile, word);
    		
    		cout<<"new word is : "<<newNode.wordFromFile<<endl;
    		
    	
    	}
    	
    
    
    inFile1.close();
    
    
    
    return 0;
    }
    
    
    
    int lookup(struct node* allNode, char target[20])
    {
    	if (allNode == NULL)
    		return (false);
    	else
    	{
    		if 
    			(strcmp (allNode->wordFromFile, target) == 0)
    				return (true);
    			else
    				if (strcmp (allNode -> wordFromFile, target) < 1)
    					return (lookup(allNode->left, target));
    				else
    					return (lookup(allNode->right, target));
    				}
    }

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    maybe looking at other code will help you some. You can search the board using the search feature above. I'm sure you'll find a fair number of hits entering binary search tree as the search string. Alternatively, I'd suggest starting out with the tutorial on lists available on this site. I think of lists as trees with no branches. Once you've mastered lists, then I'd move on to trees.
    You're only born perfect.

  8. #8
    Shake Zula- The Mic Rula!
    Join Date
    Sep 2004
    Posts
    69
    i would just like to get this code working so i can see how the code functions for real. all the stuff on the web is just the same tutorials, i can't seem to find a working model. if anyone can help me fill in the holes of this code, i'd greatly appreciate it, thanks all!

  9. #9
    Wen Resu
    Join Date
    May 2003
    Posts
    219
    i posted my tree here
    Binary Search Tree- Need Advice
    made it recently, only stores pointers to data
    I dont know how good it would be considered and it needs a function to balance it
    Check it out if you like

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree
    By ibo in forum C Programming
    Replies: 2
    Last Post: 10-12-2006, 09:55 AM
  2. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21