Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binary search tree address book interface

  1. Nov 4, 2006 #1
    I'm developing this using Visual C++ (I blew up my Ubuntu with new dist, so no linux )

    My assignment is to write an address book that is based on a binary search tree. I've written the search tree, and I've written another file that builds the address book. Thing is, I can only access the binary search tree (bst) if I include the root node in each of the functions.

    addPerson(treeNode *&root, string person)

    mind you, I've declared treeNode *root as a protected member.

    The driver that the teacher will use will access files that look more like this:

    addPerson(string person)

    so the other won't work.
    Hers is my code as it stands, with a little test program. I'm only working with the name part right now just to get basic operations to work:

    Code (Text):

    #ifndef binarySearchTree_h
    #define binarySearchTree_h

    #include <string>
    #include <iostream>

    using namespace std;

    //Define the node
    struct treeNode
    //An object of type TreeNode
    {
        string data;
        treeNode *left;
        treeNode *right;

    treeNode(string str)
            //constructor: Make a node containing str.
    {
        data = str;
        left = NULL;
        right = NULL;
    }

    };

    //define the class
    class binarySearchTree
    {
    public:
        binarySearchTree();
            //constructor
        void treeInsert(treeNode *&root, string newItem);  
            //Add an item to the binary sort tree
            //to which the parameter 'root' refers.
        void treeDelete(treeNode *&root, string deleteItem);
            //Delete an item from the binary sort tree
            //to which the parameter 'root' refers.
        void inOrderPrint(treeNode *&root);
            //Print all the items in the tree to which
            //the tree points
        int countNodes(treeNode *&root); //added int count, removed treeNode *&root
            //count the nodes in the binary tree
            //and return the answer
        bool isEmpty(treeNode *&root) const;
            //returns true if tree is empty
        bool treeContains(treeNode *&root, string data);
            //return true if item is one of the items in the
            //binary sort tree to which root points. Return
            //false if not


    protected:
        treeNode *root;
       
    };
    #endif
    #include "binarySearchTree.h"

    #include <string>
    #include <iostream>

    using namespace std;

    binarySearchTree::binarySearchTree() :root(NULL)
    {
    }
    void binarySearchTree::treeInsert(treeNode *&root, string newItem)
            //Add an item to the binary sort tree
            //to which the parameter 'root' refers.
    {
        if(root == NULL)
        {
            //the tree is empty.  Set root to point to a new node containing
            //the new item.  This becomes the only  node in the tree.

            root = new treeNode(newItem);
            //left and right subtrees of root are automatically set to NULL by
            //the constructor
            return;
        }
        else if(newItem < root->data)
        {
            treeInsert(root->left, newItem);
        }
        else
        {
            treeInsert(root->right, newItem);
        }
    }//end treeInsert

    void binarySearchTree::treeDelete(treeNode *&root, string deleteItem)
        //Delete an item from the binary sort tree
        //to which the parameter 'root' refers.
    {

        treeNode *previous, *tmp = root;

        if(root == NULL)
        {
            //the tree is empty
            cout << "The tree is empty, can't delete from an empty tree" << endl;
        }
        else if(root->right == NULL)
        {
            root = root->left;
        }
        else if(root->left == NULL)
        {
            root = root->right;
        }
        else
        {
            tmp = root->left;
            previous = root;
            while(tmp->right !=NULL)
            {
                previous = tmp;
                tmp = tmp->right;
            }
            root->data = tmp->data;
            if(previous == root)
                previous->left = tmp->left;
            else previous->right = tmp->left;
        }
        delete tmp;
    }//end deleteNode

    void binarySearchTree::inOrderPrint(treeNode *&root)
        //Print all the items in the tree to which
        //the tree points
    {
        if(root !=NULL)
                //otherwise, there is nothing to print
        {
            inOrderPrint(root->left); //prints items in left subtree
            cout << root->data << " ";//print the root item
            cout << endl;
            inOrderPrint(root->right);//print the items in rigth subtree;
        }

    }//end inOrderPrint()
    int binarySearchTree::countNodes(treeNode *&root)
        //count the nodes in the binary tree
        //and return the answer
    {
        if(root==NULL)
            return 0;  //the tree is empty
        else
        {
            int count = 1;  //start by counting the root
            count += countNodes(root->left);  //add the number of nodes
                                              //in the left subtree
            count += countNodes(root->right); //add the number of nodes
                                              //in the right subtree
            return count;  //return the total
        }
    }//end countNodes

    bool binarySearchTree::isEmpty(treeNode *&root) const
            //return true if tree is empty
    {
        return (root == NULL);
    }

    bool binarySearchTree::treeContains(treeNode *&root, string data)    
            //return true if item is one of the items in the
            //binary sort tree to which root points. Return
            //false if not
        {
            if(root==NULL)
                //tree is empty
            {
                cout << "Can't search an empty tree " << endl;
                    return false;
            }
            if(data==root->data)
                //item has been found
            {
                return true;
            }
           
            if(data < root->data)
                //item is in left subtree
            {
                return treeContains(root->left, data);
            }
            else
                //item is in right subtree
            {
                return treeContains(root->right, data);
            }
       
        } //end treeContains()

    #ifndef person_h
    #define person_h
    #include <iostream>
    #include <string>
    #include "binarySearchTree.h"

    using namespace std;

    class person: public binarySearchTree
    {
        friend ostream& operator<<(ostream&, const person&);
         
    public:
        void setPersonalInfo(treeNode *&root, string name, string address,
                          string phoneNum);
        //Function to set the details of a video.
        //The private data members are set according to the
        //parameters.
        //Postcondition:  personName = name;
        //      personAddress = address;
        //      personPhoneNum = phoneNum;
        //      numInBook = setNumInBook;
                       
        void printName(treeNode *&root) const;
        //Function to print the names located in the address book;

        void printInfo() const;
        //Function to print the name and addresses in the address book;

        bool checkName(string name);
        //Function to check if the name is already in the address book;

        string getName();
        //Function to return a name from the address book;
       
        person(string name = "" , string address = "",
                  string phoneNum = "");
        //constructor
        //The private data members are set according to the incoming parameters;
        //If no values are specified the default values are assigned.
        //Postcondition: personName = name;
        //      personAddress = address;
        //      personPhoneNum = phoneNum;
       
        void addPerson(treeNode *&root, string name); //, string address, string phoneNum);
        //Function to add a name and info to the address book;

        void deletePerson(treeNode *&root, string name);
        //Function to delete a name from the address book;

        void findPerson(treeNode *&root, string name);
        //Function to find a name located in the address book;

        void modifyPerson(string name, string address, string phoneNum);
        //Function to modify an entry in the address book;

        //overload relational operators:
        bool operator==(const person&) const;
        bool operator!=(const person&) const;
        bool operator<(const person&) const;
        bool operator<=(const person&) const;
        bool operator>(const person&) const;
        bool operator>=(const person&) const;

    private:
        string personName;          //variable to store the name;
        string personAddress;       //variable to store the address;   
        string personPhoneNum;      //variable to store the phone number;  
                       
    };

    #endif
    #include <iostream>
    #include <string>
    #include "person.h"

    using namespace std;

    /**Function to set the details of an entry.  Private members are
       set according to the parameters.
       Postcondition: personName = name;
            personAddress = address;
            personPhoneNum = phoneNum;
            numInBook = setNumInBook;
      */
    void person::setPersonalInfo(treeNode *&root, string name, string address,
                                 string phoneNum)
    {
       
        personName = name;
        personAddress = address;
        personPhoneNum = phoneNum;
    }


    /**Function to print the names located in the address book; */
    void person::printName(treeNode *&root) const
    {
       
        binarySearchTree tmp;

        tmp.inOrderPrint(root);
    }

    /**Function to print the name and addresses in the address book;*/
    void person::printInfo() const
    {
        cout<<"Name: "<< personName<<endl;
        cout<<"Address: "<< personAddress <<endl;
        cout<<"Phone Number: "<< personPhoneNum<<endl; 
    }

    /** Function to check if the name is already in the address book;  */
    bool person::checkName(string name)
    {
        return(personName == name);
    }

    /** Function to return a name from the address book;  */
    string person::getName()
    {
        return personName;
    }

    /** constructor
        The private data members are set according to the incoming parameters;
        If no values are specified the default values are assigned.
        Postcondition: personName = name;
                personAddress = address;
                personPhoneNum = phoneNum;
                numInBook = setNumInBook;  */
    person::person(string name, string address,
                         string phoneNum)
    {
        setPersonalInfo(root, name, address, phoneNum);
    }

    /**Function to add a name and info to the address book; */
    void person::addPerson(treeNode *&root, string name)
    {
        binarySearchTree tmp;
       
        tmp.treeInsert(root, name);
    }

    /**Function to delete a name from the address book; */
    void person::deletePerson(treeNode *&root, string name)
    {
        binarySearchTree tmp;
           
        tmp.treeDelete(root, name);
    }

    /**Function to find a name located in the address book;  */
    void person::findPerson(treeNode *&root, string name)
    {
        binarySearchTree tmp;
       
        if(!tmp.treeContains(root, name))
        {
            cout<<name<<" not found"<<endl;
        }
        else
            cout << name << " found" <<endl;
    }

    /**Function to modify an entry in the address book;  */
    void person::modifyPerson(string name, string address, string phoneNum)
    {
        //to be added later
    }

    /** overload the relational operators */
    bool person::operator==(const person& right) const
    {
        return (personName == right.personName);
    }

    bool person::operator!=(const person& right) const
    {
        return (personName != right.personName);
    }

    bool person::operator<(const person& right) const
    {
        return (personName < right.personName);
    }

    bool person::operator<=(const person& right) const
    {
        return (personName <= right.personName);
    }

    bool person::operator>(const person& right) const
    {
        return (personName > right.personName);
    }

    bool person::operator>=(const person& right) const
    {
        return (personName >= right.personName);
    }

    ostream& operator<<(ostream& os, const person &person)
    {
        os<<endl;
        os<<"Name: "<< person.personName <<endl;
        os<<"Address: "<< person.personAddress << endl;
        os<<"_____________________________________"<<endl;
        return os;
    }

    #include "binarySearchTree.h"
    #include "person.h"

    #include <iostream>

    using namespace std;

    int main()
    {
        person myList;
        binarySearchTree list;
        treeNode *root;  //pointer to the root noode in the tree
        root = NULL;  //start with an empty tree
        string someName;
        int choice;
        int num = 0;
       
        cout << "What would you like to do? "<< endl;
        cout << "1=insert" << endl;
        cout << "2=count the nodes" << endl;
        cout << "3=print the nodes" << endl;
        cout << "4=delete a node" << endl;
        cout << "5=find a name" << endl;
        cout << "9=exit "<< endl;
        cout << endl;
        cin >> choice;
        cin.ignore(100, '\n');
        while(choice !=9)
        {
            switch (choice)
            {
            case 1: cout << "Enter a name for the list: " ;
                    getline(cin, someName);
                    myList.addPerson(root, someName);
                    break;

            case 2: cout << "The number of nodes in the tree are: ";
                    num =  list.countNodes(root);
                    cout << num ;
                    break;

            case 3: cout << "Here is the list: " << endl;
                    myList.printName(root);
                    break;

            case 4: cout << "What item to delete? ";
                    getline(cin, someName);
                    myList.deletePerson(root, someName);
                    cout << someName << "is deleted." << endl;
                    myList.printName(root);
                    break;
            case 5: cout << "What name are you searching for? ";
                    getline(cin, someName);
                    myList.findPerson(root, someName);
                    break;

            default: cout << "Invalid selection" << endl;
           
            } //end switch

        cout << endl;
        cout << "What would you like to do? "<< endl;
        cout << "1=insert" << endl;
        cout << "2=count the nodes" << endl;
        cout << "3=print the nodes" << endl;
        cout << "4=delete a node" << endl;
        cout << "9=exit "<< endl;
        cout << endl;
        cin >> choice;
        cin.ignore(100, '\n');
        cout << endl;
        }//end while
       

        cout << endl;
        return 0;
    }
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted



Similar Discussions: Binary search tree address book interface
  1. Binary tree algoritms (Replies: 5)

  2. Binary Search Tree C++ (Replies: 1)

  3. Binary tree (Replies: 5)

Loading...