Binary Search Tree File Reading

[ace8957]

Hi all,

So I have reached a kind of impasse on my current project. I'm trying to make a program that can function like a phone book, loading information from a file into a binary search tree and performing operations on said information.

The issue I'm having appears to be fairly simple at the moment.
I have a function called fillTree which runs at the beginning of the program and should be able to fill the binary search tree with the data from the text file. However, as soon as this function exits, the data disappear, leaving me bemused and confused. When I attempt the print the contents of the tree, it appears empty.

fillTree() calls the function BinarySearchTree::insert(Person) which works well enough under other circumstances. It appears to be the combination of these two functions that is causing some sort of error, resulting in the tree not filling properly.

If anyone has any input on this, it would be greatly appreciated.

Here is my code (all one big file at this point for convenience):

//Binary Search Tree Program

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <stdio.h>
using namespace std;

typedef string treeType;

class Person{
    private:
    string name;
    int phonenumber;
    public:
    Person();
    Person(string name, int phonenumber);
    string getName();
    int getPhonenumber();
    void setName(string newname);
    void setPhonenumber(int newphonenumber);
};

class BinarySearchTree
{
    private:
        struct tree_node
        {
           tree_node* left;
           tree_node* right;
           //treeType data;
           Person data;

        };
        tree_node* root;

    public:
        BinarySearchTree()
        {
           root = NULL;
        }

        bool isEmpty() const { return root==NULL; }
        void print_inorder();
        void inorder(tree_node*);
        void print_preorder();
        void preorder(tree_node*);
        void print_postorder();
        void postorder(tree_node*);
        void insert(Person);
        void remove(string);
        void search(string key);
        void changePhonenumber(string key, int newnumber);
};

Person::Person()
{
}

Person::Person(string newname, int newphonenumber)
{
    name = newname;
    phonenumber = newphonenumber;
}

string Person::getName() {
    return name;
}

int Person::getPhonenumber() {
    return phonenumber;
}

void Person::setName(string newname) {
    name = newname;
}

void Person::setPhonenumber(int newphonenumber) {
    phonenumber = newphonenumber;
}

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(Person p)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = p;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;

    // is this a new tree?
    if(isEmpty()) root = t;
    else
    {
        //Note: ALL insertions are as leaf nodes
        tree_node* curr;
        curr = root;
        // Find the Node's parent
        while(curr)
        {
            parent = curr;
            if(t->data.getName() > curr->data.getName()) curr = curr->right;
            else curr = curr->left;
        }

        if(t->data.getName() < parent->data.getName())
           parent->left = t;
        else
           parent->right = t;
    }
}

void BinarySearchTree::remove(string p)
{
    //Locate the element
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }

    tree_node* curr;
    tree_node* parent;
    curr = root;

    while(curr != NULL)
    {
         if(curr->data.getName() == p)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(p>curr->data.getName()) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found)
		 {
        cout<<" Data not found! "<<endl;
        return;
    }


		 // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children

    // Node with single child
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else // left child present, no right child
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
     return;
    }

		 //We're looking at a leaf node
		 if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
		 		 delete curr;
		 		 return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else // right child has children
        {
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }
		curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               curr->data = tmp->data;
	       curr->right = tmp->right;
               delete tmp;
           }

        }
		 return;
    }

}

void BinarySearchTree::print_inorder()
{
  inorder(root);
}

void BinarySearchTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<<p->data.getName()<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}

void BinarySearchTree::print_preorder()
{
    preorder(root);
}

void BinarySearchTree::preorder(tree_node* p)
{
    if(p != NULL)
    {
        cout<<" "<<p->data.getName()<<" ";
        if(p->left) preorder(p->left);
        if(p->right) preorder(p->right);
    }
    else return;
}

void BinarySearchTree::print_postorder()
{
    postorder(root);
}

void BinarySearchTree::postorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) postorder(p->left);
        if(p->right) postorder(p->right);
        cout<<" "<<p->data.getName()<<" ";
    }
    else return;
}

//////////////////new/////////////////////////
void BinarySearchTree::search(string key)
{
     bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }

    tree_node* curr;
    tree_node* parent;
    curr = root;

    while(curr != NULL)
    {
         if(curr->data.getName() == key)
         {
            found = true;
            cout << "The phone number for " << key << " is " << curr->data.getPhonenumber() << endl;
            break;
         }
         else
         {
             parent = curr;
             if(key>curr->data.getName()) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found)
		 {
        cout<<" Data not found! "<<endl;
        return;
    }
}

void BinarySearchTree::changePhonenumber(string p, int newnumber) {
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }

    tree_node* curr;
    tree_node* parent;
    curr = root;

    while(curr != NULL)
    {
         if(curr->data.getName() == p)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(p>curr->data.getName()) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found)
		 {
        cout<<" Person not found. "<<endl;
        return;
    }

    //change the phonenumber associated with the node
    curr->data.setPhonenumber(newnumber);
    cout<< "Number changed successfully. " << endl;
}//end changePhonenumber

/////////////////////////////////////new add into book class//////////////
void fillTree( BinarySearchTree b)
{
    ifstream file;
    file.open("phonebook.txt");
    if(!file) {
        cout<<" Error opening file. " << endl;
    }
    //variables used to load data into the tree
    string name;
    int phonenumber;
    Person p;
    while(file >> name >> phonenumber)
    {
        p.setName(name);
        p.setPhonenumber(phonenumber);
        cout << p.getName() << "  " << p.getPhonenumber() << endl;
        b.insert(p);
    }
    file.close();
}

int main()
{
    BinarySearchTree b;
    int ch;
    string name;
    string key;
    int phonenumber;
    Person tmp;
    Person tmp1;
    fillTree(b);
    b.print_preorder();
    while(1)
    {
       cout<<endl<<endl;
       cout<<" Binary Search Tree Operations "<<endl;
       cout<<" ----------------------------- "<<endl;
       cout<<" 0. Search             "<<endl;
       cout<<" 1. Insertion/Creation "<<endl;
       cout<<" 2. In-Order Traversal "<<endl;
       cout<<" 3. Pre-Order Traversal "<<endl;
       cout<<" 4. Post-Order Traversal "<<endl;
       cout<<" 5. Removal "<<endl;
       cout<<" 6. Change a Phonenumber "<<endl;
       cout<<" 7. Exit "<<endl;
       cout<<" Enter your choice : ";
       cin>>ch;
       switch(ch)
       {
           case 0 : cout <<" Enter the name of the person to search for: "<<endl;
                    cin>>key;
                    b.search(key);
                    break;
           case 1 : cout<<" Enter name to be inserted: ";
                    cin>>name;
                    cout << endl << " Enter phone number: " << endl;
                    cin >> phonenumber;
                    tmp.setName(name);
                    tmp.setPhonenumber(phonenumber);
                    b.insert(tmp);
                    break;
           case 2 : cout<<endl;
                    cout<<" In-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    b.print_inorder();
                    break;
           case 3 : cout<<endl;
                    cout<<" Pre-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    b.print_preorder();
                    break;
           case 4 : cout<<endl;
                    cout<<" Post-Order Traversal "<<endl;
                    cout<<" --------------------"<<endl;
                    b.print_postorder();
                    break;
           case 5 : cout<<" Enter data to be deleted : ";
                    //cout << "Deletion needs to be implemented." << endl;
                    cin>>key;
                    b.remove(key);
                    break;
           case 6 : cout<<" Enter the name of the person whose number you wish to change: " <<endl;
                    cin>>name;
                    cout<<endl<<" Enter the new phonenumber: " <<endl;
                    cin>>phonenumber;
                    cout<<endl;
                    b.changePhonenumber(name, phonenumber);
                    break;
           case 7 : return 0;

       }
    }
}

and here are the contents of phonebook.txt

Adam 1
Bob 2
Frank 3
Thomas 4
John 5
Shawn 6
Sean 7
Joshua 8
Phillip 9
Jacob 10

If anybody has any input at all about this, it would be greatly appreciated.

[group256]

First of all, thank you for your easy to read explanation and providing all the code and information needed. Your problem is that you should send the address of your "b" value if you don't want to return anything from your function(Let me know if you still need more information regarding this). I did the modification and works, change the indicated lines and try again:

void fillTree( BinarySearchTree *b)//Line 368

and

(*b).insert(p); //Line 384

finally

fillTree(&b); // Line 398

[ace8957]

Thanks a bunch! Works like a charm. I'm still not entirely clear on why that made it work when b.insert(tmp) on line 427 works, but I'll roll with it. I'm going to assume that since I'm not calling the BinarySearchTree function correctly I need to pass in the address so that it can be modified by an outside function.

[group256]

hmmm... let me explain in my words, then I think it would not be hard for you to look up more details with help of google.

OK, first thing is scope. When you define a function and you give some parameters, those parameters are only accessible within the function. Look at the code:

int myFunc(int i, int j, int sum)
{
  sum = i + j;
}

So in here, all the 3 variables exist as long as the function running, as soon as the function is terminated, the values in memory addresses referring to i, j, and sum vanish(or at least they are not visible anymore). So, let's say you need the value of sum, what can you do??? One way is to return a value from the function. So just add the line:

return sum;

at the end of above code and that's it.

But there is another way; the way, is instead of creating a new sum, pass the ADDRESS of sum, make the modification and as the function and the calling method are both pointing to the same address, the value in that address is accessible by both. Ex:

int myFun(int i, int j, int* sum) //Asterik means that the function expects to receive an ADDRESS not a value.
{
  *sum = i + j; //That's it!!!
}

int main()
{
  int i = 10, j = 20, sum;
  myFun(i, j, &sum); // Send the address of sum instead of its value!!!

  cout << "Sum is: " << sum;
}

Now what happens is, you are telling the function to go to a specific address, change some values and leave it there, so the main function could use it too.

I hope this explanation was clear enough.

[ace8957]

That was a very clear explanation. It appears I had a retard moment and just forgot all about how main() itself is a function and that the BinarySearchTree instance is a local data member of main. Thanks again!