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

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.

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

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;

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

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

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.

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!

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