The two classes from the bintree3.cpp program are displayed below. Please add another method to the BT class which will count the number of active nodes that are included in the current binary tree and will propagate that count to the calling program. The method will have the name countNodes and it will have one parameter whose variable type will be determined by you. Please write its signature line for the Queue class definition and write its full method definition separately.
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
Code:
class Node {
private:
string val; // current value in collating sequence
Node* lh; // pointer to left-hand descendant Node
Node* rh; // pointer to right-hand descendant Node
public:
Node () { lh = rh = NULL; val = '\0'; } // Node () {}
void putVal (string v) { val = v; }
string getVal () { return val; }
void putLH (Node* x) { lh = x; }
Node* getLH () { return lh; }
void putRH (Node* x) { rh = x; }
Node* getRH () { return rh; }
void write (void) { cout << " " << val; }
};
class BT {
private:
int count;
Node* root;
Node* tree;
Node* addNode (Node*, string);
Node* findInsertion (Node* tree, string v);
void inOrder (Node*);
void preOrder (Node*);
void postOrder (Node*);
void locate (Node*, string);
public:
BT ();
void addNodeRoot (string);
void inOrderTraverse ();
void preOrderTraverse ();
void postOrderTraverse ();
int getCount () { return count; }
void locateRoot (string);
};
BT::BT () { root = tree = NULL; count = 0; } // BT::BT () {}
void BT::addNodeRoot (string v)
{ if (root == NULL)
{root = tree = addNode (tree, v);
// cout << "ptr to root " << root << endl;
}
else
{ tree = root;
tree = findInsertion (tree, v);
} }
void BT::locateRoot (string v) {
if ( root == NULL )
cout << "Tree is empty" << endl;
else
locate ( root, v );
}
void BT::locate (Node* y, string v) { // Bug mentioned by Dan Glade
string x;
x = y -> getVal ();
if ( v == x )
cout << "Value " << v << " is in Node at address " << (int)y << endl;
else if ( v <= x )
if ( y -> getLH() != NULL )
locate (y-> getLH(), v);
else
cout << "Value not in tree" << endl;
else // if ( v > x )
if ( y -> getRH() != NULL )
locate ( y-> getRH(), v );
else
cout << "Value not in tree" << endl;
}
Node* BT::findInsertion (Node* tree, string v)
{ string x;
x = tree -> getVal();
// cout << count << " compare " << v << " and " << x << endl;
if ( v <= x )
if( tree -> getLH () !=NULL )
tree = findInsertion (tree -> getLH(), v);
else
{ Node* temp = NULL;
temp = addNode (temp, v);
tree ->putLH(temp); }
if ( v > x )
if (tree -> getRH () !=NULL )
tree = findInsertion (tree -> getRH(), v);
else
{ Node* temp = NULL;
temp = addNode (temp, v);
tree ->putRH(temp); }
return tree; }
Node* BT::addNode (Node* x, string v)
{ if (x = new Node)
{ x->putVal (v);
++count;
// cout << count << " " << x << " " << x->getVal () << endl;
x->putLH(NULL);
x->putRH(NULL); }
return x; }
void BT::inOrderTraverse ()
{ tree = root;
inOrder (root); }
void BT::inOrder (Node* n)
{ if (n == NULL) return;
inOrder (n->getLH());
n->write ();
inOrder (n->getRH()); }
void BT::preOrderTraverse ()
{ tree = root;
preOrder (root); }
void BT::preOrder (Node* n)
{ if (n == NULL) return;
n->write ();
preOrder (n->getLH());
preOrder (n->getRH()); }
void BT::postOrderTraverse ()
{ tree = root;
postOrder (root); }
void BT::postOrder (Node* n)
{ if (n == NULL) return;
postOrder (n->getLH());
postOrder (n->getRH());
n->write (); }
int main () {
string x;
BT TREE;
Node* test;
// Create inorder Binary treee
cout << "To create your Binary tree, enter each "
<< "character of your list" << endl;
cout << "To terminate your list hit <Enter> then control-z <Enter>"
<< endl;
while (!cin.eof())
{ cin >> x;
if (!cin.eof())
TREE.addNodeRoot (x);
}
if ( TREE.getCount ())
{ cout << endl
<< "In-Order Tree Traversal" << endl;
TREE.inOrderTraverse ();
cout << endl;
cout << "Pre-Order Tree Traversal" << endl;
TREE.preOrderTraverse();
cout << endl;
cout << "Post-Order Tree Traversal" << endl;
TREE.postOrderTraverse();
cout << endl << "Enter User value of Node to locate ";
cin.clear();
cin >> x;
if (!cin.eof())
TREE.locateRoot ( x );
}
else
cout << endl << "Tree is empty. No characters found.";
cout << endl;
system("PAUSE");
return EXIT_SUCCESS;
}
I am very new at this so any help is greatly appreciated to get me off on the right foot, thanks!