I have to create preorder(), inOrder()[ these need to be used with the traversal
ID: 3670034 • Letter: I
Question
I have to create preorder(), inOrder()[ these need to be used with the traversal algorithm] , nodeCount()[count the number of nodes in a binary search tree. In this function, you should use a recursive function.] and search()-- recursively.
Below i have implemented or tried to start these. In my header I switched it around and added the nodes on the bottom but for whatever reason it is not recognizing BST::search() or any of the member functions from the header file. Can you please explain why? help please. Included is my header, source and tester file.
BST.h
#include <iostream>
using namespace std;
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
class BST
{
/***** Node class *****/
class BinNode
{
public:
int data;
BinNode * left;
BinNode * right;
// BinNode constructors
// Default -- data part is default int value; both links are null.
BinNode()
: left(0), right(0)
{}
// Explicit Value -- data part contains item; both links are null.
BinNode(int item)
: data(item), left(0), right(0)
{}
};// end of class BinNode declaration
public:
/***** Function Members *****/
BST();
bool empty() const;
bool search(const int & item);
void insert(const int & item);
void inOrder(BinNode *myRoot);
void preOrder(BinNode *myRoot);
int nodeCount(BinNode *myRoot);
/***** Data Members *****/
BinNode * myRoot;
private:
bool search(const int & item, BinNode * root);
}; // end of class declaration
// end of class declaration
#endif
BST.cpp
#include <iostream>
#include <iomanip>
using namespace std;
#include "BST.h"
//--- Definition of constructor
BST::BST()
: myRoot(0)
{}
bool BST::empty() const
{ return myRoot == 0; }
void BST:: preOrderTrav()
{
preOrder(myRoot);
}
void BST:: preOrder()
{
BinNode *ptr;
if (myRoot != NULL)
{
cout<< myRoot->data<< " ";
preOrder(myRoot->left());
preOrder(myRoot->right());
}
}
void BST::inOrder()
{
BinNode *myptr;
if(myRoot == NULL)
{
cout<< " empty"<<endl;
return;
}
if(myptr != NULL)
{
( myptr->left);
cout<< myptr-> data<< " ";
return ( myptr-> right);
}
}
bool BST::search(const int & item, BinNode *root) const
{
if ( root == NULL)
{
return false;
}
else if (item == root->data)
{
return true;
}
else if (item < root->data)
{
}
/* //BinNode * locptr = myRoot;
//bool found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
return (locptr->left);
else if (locptr->data < item) // descend right
return(locptr->right);
else // item found
found = true;
}
return found;*/
}
bool BST::search(int key)
{
}
int BST::nodeCount()
{
int count = 0;
BinNode *locptr = myRoot;
if(locptr !=NULL)
{
cout += nodeCount(myRoot->left);
cout += nodeCount(myRoot->right);
return count;
}
//return count;
}
void BST::insert(const int & item)
{
BinNode * locptr = myRoot; // search pointer
BinNode * parent = 0; // pointer to parent of current node
bool found = false; // indicates if item already in BST
while (!found && locptr != 0)
{
parent = locptr;
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
if (!found)
{ // construct node containing item
locptr = new BinNode(item);
if (parent == 0) // empty tree
myRoot = locptr;
else if (item < parent->data ) // insert to left of parent
parent->left = locptr;
else // insert to right of parent
parent->right = locptr;
}
else
cout << "Item already in the tree ";
}
/*----- treetester.cpp -----------------------------------------------------
Program for testing BST.
------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include "BST.h"
int main()
{
// Testing Constructor and empty()
BST intBST; // test the class constructor
intBST.insert(10);
intBST.insert(12);
intBST.insert(5);
intBST.insert(1);
intBST.insert(20);
intBST.insert(30);
Explanation / Answer
Hi. try with given below command to compile :
If you say g++ main.cpp and this is your whole command line, the error is a linker error that it can't find favNum, right? In that case, try:
g++ main.cpp favourite.cpp
or split compilation and linking:
g++ -c main.cpp -o main.o
g++ -c favourite.cpp -o favourite.o
g++ main.o favourite.o
Where -c means: Compile only, no linking and -ofilename is required because you want to write the output to two different object files to link them with the last command.
if above not works, try this
To compile separately without linking you need to add -c option: