Hi Folks,
I am working on a binary search tree assignment that is supposed to use recursion. My code compiles but will not insert more than one item, search or display. I am thinking I am having a problem with my tree not being linked together properly.
As for my displays, in my main program, I created a variable root of type TNode....so that is what I am calling my functions with...but I am thinking that is wrong because it doesn't call up my tree when i go to display. I am not sure how to call my tree for those.
I apologize in advance for the lack of comments. My right arm is in a sling atm due to torn cartilage in my shoulder so I am doing this all by pecking at the keyboard with one hand.
I have tried searching and looking around on the internet at tutorials, but I am still not getting it. If anyone can just even take a look at my insert function, that would be a huge help. Any hints, nudges or kicks into the right direction would be greatly appreciated.
Here is the header file
CODE
//*************************************************************************
//Header file BSTree.h with specifications for class BSTree *
//*************************************************************************
#include <iostream> //allows the program to input and output
#include <conio.h> //allows the program to input and output from console
using std::cout; //allows for output
using std::cin;//allows for input
using std::endl;//ends a line and dumps the data*/
typedef int itemType; //defines itemType as int
class BSTree
{
private:
struct TNode
{
itemType item;
TNode *lchild;
TNode *rchild;
};//end struct TNode
int size; //size variable tracks number of nodes
TNode *root;
TNode *p;
TNode *q;
public://public accessor
BSTree();
//Goal:
//Pre:
//Post:
bool isEmpty() const;
//Goal:
//Pre:
//Post:
bool isFull() const;
//Goal:
//Pre:
//Post
void insert(TNode *p, itemType newItem);
//Goal:
//Pre:
//Post:
itemType search(TNode *p, itemType newItem);
//Goal:
//Pre:
//Post:
int getSize();
//Goal:
//Pre:
//Post:
void displayInorder(TNode *p);
//Goal:
//Pre:
//Post:
void displayPreorder(TNode *p);
//Goal:
//Pre:
//Post:
void displayPostorder(TNode *p);
//Goal:
//Pre:
//Post
};
Here is the Implementation File
CODE
//*************************************************************************
//Implementation file BSTree.cpp with implementation of class BSTree *
//*************************************************************************
#include "BSTree.h" //includes class specifications
#include <iostream> //allows the program to input and output
#include <conio.h> //allows the program to input and output from console
using std::cout; //allows for output
using std::cin;//allows for input
using std::endl;//ends a line and dumps the data*/
BSTree::BSTree() //constructor
{
size = 0; //sets size counter to zero
root = NULL;
}
bool BSTree::isEmpty() const
{
return (size == 0); //returns true when size variable is empty
}
bool BSTree::isFull() const
{
return false; //always returns false
}
void BSTree::insert(TNode *p, itemType newItem)
{
if(isEmpty())
{
root = new TNode;
root->item = newItem;
root->lchild = NULL;
root->rchild = NULL;
size++;
}
else if(p == NULL)
{
p = new TNode;
p->item = newItem;
p->lchild = NULL;
p->rchild = NULL;
size++;
/*here is where I am trying to keep the tree
connected with the trailing pointer*/
if(p->item <q->item)
{
q->lchild = p;
}
else
{
q->rchild = p;
}
}
else if (newItem < p->item)
{
q = p;//trailing pointer
//search left side of tree
insert(p->lchild, newItem);
}
else //search right side of treee
{
q=p; //trailing pointer
insert(p->rchild, newItem);
}
}
itemType BSTree::search(TNode *p, itemType newItem)
{
if(!isEmpty())
{
if(p->item == newItem)
{
return p->item;
}
else if(newItem < p->item)
{
search(p->lchild, newItem);
}
else //search rightside of tree
{
search(p->rchild, newItem);
}
}
else //tree is empty
{
cout << "Tree is empty." << endl;
}
}
int BSTree::getSize()
{
return size;
}
void BSTree::displayInorder(TNode *p)
{
if(!isEmpty())
{
//invisible basis of if p == NULL
if(p!=NULL)
{
displayInorder(p->lchild); //visit right subtree
cout << p->item; //visit node
displayInorder(p->rchild); //visit right subtree
}
}
else //tree is Empty
{
cout << "\nTree is Empty\n" << endl;
}
}
void BSTree::displayPreorder(TNode *p)
{
if(!isEmpty())
{
//invisible basis of if p == NULL
if(p!=NULL)
{
cout << p->item; //visit node
displayPreorder(p->lchild); //visit left subtree
displayPreorder(p->rchild); //visit right subtree
}
}
else //tree is Empty
{
cout << "\nTree is Empty\n" << endl;
}
}
void BSTree::displayPostorder(TNode *p)
{
if(!isEmpty())
{
//invisible basis of if p == NULL
if(p!=NULL)
{
displayPostorder(p->lchild); //visit left subtree
displayPostorder(p->rchild); //visit right subtree
cout << p->item; //visit node
}
}
else //tree is Empty
{
cout << "\nTree is Empty\n" << endl;
}
}
and my main file
CODE
//*************************************
//Main file testing class BSTree *
//*************************************
#include "BSTree.h" //includes class specifications
#include <iostream> //allows the program to input and output
#include <conio.h> //allows the program to input and output from console
using std::cout; //allows for output
using std::cin;//allows for input
using std::endl;//ends a line and dumps the data*/
//begin main function
int main()
{
int choice; //creates variable choice for switch statement
itemType anItem; //creates variable anItem
struct BSTree::TNode *root;
root = NULL;
BSTree testBSTree; //constructs an object from class BSTree
do{
//Prompts the user to choose an option
cout << "\n1. Insert" << endl;
cout << "2. Search" << endl;
cout << "3. Get Size" << endl;
cout << "4. Display list in order" << endl;
cout << "5. Display list postorder" <<endl;
cout << "6. Display list preorder" << endl;
cout << "7. Quit" << endl;
cout << "Enter the number of the function you would like to choose: ";
cin >> choice;//allows user to input their choice
switch(choice)//begin case statements
{
case 1:
cout << "\nEnter an integer you would like to insert into tree: ";//prompts the user for integer to insert
cin >> anItem;//receives the integer from user
testBSTree.insert(root,anItem);//calls insert function
break; //end case 1
case 2://begin case 2
cout << "\nEnter an integer you would like to search for: ";//prompts the user for integer to insert
cin >> anItem;//receives the integer from user
if(testBSTree.search(root, anItem) == anItem) //prevents displaying garbage
{
cout << "A " << testBSTree.search(root, anItem) << " has been found in the list!"; //tests remove function
}
else
{
cout << "Unable to find " << anItem << endl;
}
break;//end case 2
case 3: //begin case 3
cout << "\n\nThe size of your tree is " << testBSTree.getSize() << "." << endl; //tests getSize function
break;//end case 3
case 4: //begin case 4
testBSTree.displayInorder(root);
break;//end case 4
case 5: //begin case 5
testBSTree.displayPreorder(root);
break; //end case 5
case 6: //begin case 6
testBSTree.displayPreorder(root);
break; //end case 6
case 7: //begin case 8
cout << "Press any key to exit" << endl;
break; //end case 8
}
}while(choice != 7); //exits the program
//getch(); //gets the enter character
return 0;
}//end of main function
| 