Help with Binary Search Tree insertion

**bcianfrocca** · 05-11-2005

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

**hk_mp5kpdw** · 05-11-2005

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.

**bcianfrocca** · 05-11-2005

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...

**elad** · 05-11-2005

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;

**bcianfrocca** · 05-11-2005

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;
}

**bcianfrocca** · 05-11-2005

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

**elad** · 05-11-2005

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.

**bcianfrocca** · 05-11-2005

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!

**Iamien** · 05-11-2005

i posted my tree here
http://cboard.cprogramming.com/showthread.php?t=65386
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

Thread: Help with Binary Search Tree insertion

Thread Tools

Search Thread

Display

Help with Binary Search Tree insertion

Similar Threads

Binary Search Tree

searching and insertion in a binary search tree

Request for comments

Binary Search Tree, Inserting node

BST/Red and Black Tree