There's smthg wrong in the main but i dnt know what
Write a class Employee having ID (int), name(string) and salary(int) as private data members. Provide a constructor with default value, a set function, and overload the output and input streams.
Write two comparator classes for Employee according to Salary, one class two compare the two salaries of two employees, and another to compare and int value to an Employee salary.
In main declare a bst having the 4 template parameters as follows:
BST<int, employee, employeeIntCompare, employeeCompare> tree;
and populate its initial values from a file having the following data: (ID, name, salary)
23 abed 1500
56 samir 2000
41 zeina 1100
76 abir 1350
14 mounir 1200
98 sawsan 780
18 fahim 680
51 hasan 1750
11 suheil 950
First print the resulting bst (with indented levels, it is a bonus)
Then write a repetitive menu having the following options:
• Insert a new Employee (input the 3 values using the overloaded cin, then insert it
• Search by salary for an employee, make use of the comparator class
• Delete an Employee having a specific salary.
• Print the existing tree in the 3 traversal modes. (in ,pre, post)
When the user chooses to quit, print out the tree in inorder traversal to a file called output.txt before quitting.
Finally, think!
BST Property: All elements stored in the left subtree of a node with value K have values < K. All elements stored in the right subtree of a node with value K have values K.
If we want to make a small modification on the BST property so that now we will have:
BST Property: All elements stored in the left subtree of a node with value K have values ≤ K. All elements stored in the right subtree of a node with value K have values K.
What do we have to modify in the BST implementation? Explain (as a comment in your coding) and test.
[main]
#include <iostream>
#include <string>
#include <fstream>
#include " bs2.h "
using namespace std;
class employee
{
private:
int ID;
int salary;
string name;
public:
employee(){
ID=0;
salary=0;
name="notfound";
}
void set (int e, int f, string g){
ID=e;
salary=f;
name=g;
}
int salaryis (){
return salary;
}
friend ostream& operator<<(ostream& s, const employee& i) //overloading output
{
s<<"(ID: "<<i.ID<<" Name: "<<i.name<<" Fees: "<<i.salary<<")\n";
return s;
}
friend istream& operator>>(istream& s, employee& i) //overloading input
{
cout<<"enter employee ID, then name then salary:\n";
s>>i.ID>>i.name>>i.salary;
return s;
}
};
class EmployeeComparision
{
public:
static bool eq( employee a , employee b )
{ return a.salaryis()==b.salaryis(); }
static bool lt( employee a , employee b )
{ return a.salaryis()<b.salaryis(); }
static bool gt( employee a , employee b )
{ return a.salaryis()>b.salaryis(); }
};
class EmployeeIntComparision
{
public:
static bool eq( employee g , int h )
{ return g.salaryis()==h; }
static bool lt( employee g , int h )
{ return g.salaryis()<h; }
static bool gt( employee g , int h )
{ return g.salaryis()>h; }
};
void main ()
{
ifstream inFile;
ofstream outFile;
BST<int, employee, employeeIntCompare, employeeCompare> tree;
inFile.open("test.txt");
outFile.open("testavg.txt");
employee gaelle;
for (int i=0; i<9; i++)
{
inFile>>gaelle;
tree.insert(gaelle);
}
tree.print();
int choice;
while(1)
{
cout<<"\n Enter 1 to insert a new Employee \n";
cout<<"Enter 2 to search by salary for an employee\n";
cout<<"Enter 3 to delete an Employee having a specific salary.\n";
cout<<"Enter 4 to print the existing tree in the 3 traversal modes.\n";
cout<<"Enter 0 to quit\n";
cin>>choice;
if (choice==0)
{
outFile <<tree.print()<<endl;
break;
}
if (choice==1)
{
employee chedid;
cin>>chedid;
tree.insert(chedid);
}
if (choice==3)
{
cout<<"enter the salary of the employee that needs to be deleted"<<endl;
int j;
cin>>j;
tree.remove(j, employee e);
}
if (choice==4)
{
tree.print();
}
}
}
//we need to replace all the < by <= and all the >= by > in all the functions
[/main]
[dictionary]
// The Dictionary abstract class. KEComp compares a key
// and an element. EEComp compares two elements.
template <class Key, class Elem, class KEComp, class EEComp>
class Dictionary {
public:
// Reinitialize dictionary
virtual void clear() = 0;
// Insert an element. Return true if insert is
// successful, false otherwise.
virtual bool insert(const Elem&) = 0;
// Remove some element matching Key. Return true if such
// exists, false otherwise. If multiple entries match
// Key, an arbitrary one is removed.
virtual bool remove(const Key&, Elem&) = 0;
// Remove and return an arbitrary element from dictionary.
// Return true if some element is found, false otherwise.
virtual bool removeAny(Elem&) = 0;
// Return a copy of some Elem matching Key. Return true
// if such exists, false otherwise. If multiple elements
// match Key, return an arbitrary one.
virtual bool find(const Key&, Elem&) const = 0;
// Return the number of elements in the dictionary.
virtual int size() = 0;
};
[/dictionary]
Write two comparator classes for Employee according to Salary, one class two compare the two salaries of two employees, and another to compare and int value to an Employee salary.
In main declare a bst having the 4 template parameters as follows:
BST<int, employee, employeeIntCompare, employeeCompare> tree;
and populate its initial values from a file having the following data: (ID, name, salary)
23 abed 1500
56 samir 2000
41 zeina 1100
76 abir 1350
14 mounir 1200
98 sawsan 780
18 fahim 680
51 hasan 1750
11 suheil 950
First print the resulting bst (with indented levels, it is a bonus)
Then write a repetitive menu having the following options:
• Insert a new Employee (input the 3 values using the overloaded cin, then insert it
• Search by salary for an employee, make use of the comparator class
• Delete an Employee having a specific salary.
• Print the existing tree in the 3 traversal modes. (in ,pre, post)
When the user chooses to quit, print out the tree in inorder traversal to a file called output.txt before quitting.
Finally, think!
BST Property: All elements stored in the left subtree of a node with value K have values < K. All elements stored in the right subtree of a node with value K have values K.
If we want to make a small modification on the BST property so that now we will have:
BST Property: All elements stored in the left subtree of a node with value K have values ≤ K. All elements stored in the right subtree of a node with value K have values K.
What do we have to modify in the BST implementation? Explain (as a comment in your coding) and test.
[main]
#include <iostream>
#include <string>
#include <fstream>
#include " bs2.h "
using namespace std;
class employee
{
private:
int ID;
int salary;
string name;
public:
employee(){
ID=0;
salary=0;
name="notfound";
}
void set (int e, int f, string g){
ID=e;
salary=f;
name=g;
}
int salaryis (){
return salary;
}
friend ostream& operator<<(ostream& s, const employee& i) //overloading output
{
s<<"(ID: "<<i.ID<<" Name: "<<i.name<<" Fees: "<<i.salary<<")\n";
return s;
}
friend istream& operator>>(istream& s, employee& i) //overloading input
{
cout<<"enter employee ID, then name then salary:\n";
s>>i.ID>>i.name>>i.salary;
return s;
}
};
class EmployeeComparision
{
public:
static bool eq( employee a , employee b )
{ return a.salaryis()==b.salaryis(); }
static bool lt( employee a , employee b )
{ return a.salaryis()<b.salaryis(); }
static bool gt( employee a , employee b )
{ return a.salaryis()>b.salaryis(); }
};
class EmployeeIntComparision
{
public:
static bool eq( employee g , int h )
{ return g.salaryis()==h; }
static bool lt( employee g , int h )
{ return g.salaryis()<h; }
static bool gt( employee g , int h )
{ return g.salaryis()>h; }
};
void main ()
{
ifstream inFile;
ofstream outFile;
BST<int, employee, employeeIntCompare, employeeCompare> tree;
inFile.open("test.txt");
outFile.open("testavg.txt");
employee gaelle;
for (int i=0; i<9; i++)
{
inFile>>gaelle;
tree.insert(gaelle);
}
tree.print();
int choice;
while(1)
{
cout<<"\n Enter 1 to insert a new Employee \n";
cout<<"Enter 2 to search by salary for an employee\n";
cout<<"Enter 3 to delete an Employee having a specific salary.\n";
cout<<"Enter 4 to print the existing tree in the 3 traversal modes.\n";
cout<<"Enter 0 to quit\n";
cin>>choice;
if (choice==0)
{
outFile <<tree.print()<<endl;
break;
}
if (choice==1)
{
employee chedid;
cin>>chedid;
tree.insert(chedid);
}
if (choice==3)
{
cout<<"enter the salary of the employee that needs to be deleted"<<endl;
int j;
cin>>j;
tree.remove(j, employee e);
}
if (choice==4)
{
tree.print();
}
}
}
//we need to replace all the < by <= and all the >= by > in all the functions
[/main]
[dictionary]
// The Dictionary abstract class. KEComp compares a key
// and an element. EEComp compares two elements.
template <class Key, class Elem, class KEComp, class EEComp>
class Dictionary {
public:
// Reinitialize dictionary
virtual void clear() = 0;
// Insert an element. Return true if insert is
// successful, false otherwise.
virtual bool insert(const Elem&) = 0;
// Remove some element matching Key. Return true if such
// exists, false otherwise. If multiple entries match
// Key, an arbitrary one is removed.
virtual bool remove(const Key&, Elem&) = 0;
// Remove and return an arbitrary element from dictionary.
// Return true if some element is found, false otherwise.
virtual bool removeAny(Elem&) = 0;
// Return a copy of some Elem matching Key. Return true
// if such exists, false otherwise. If multiple elements
// match Key, return an arbitrary one.
virtual bool find(const Key&, Elem&) const = 0;
// Return the number of elements in the dictionary.
virtual int size() = 0;
};
[/dictionary]
[bs2.h]
// This file includes all of the pieces of the BST implementation
#include "dictionary.h"
#include "binnode.h"
// Binary Search Tree implementation for the Dictionary ADT
template <class Key, class Elem, class KEComp, class EEComp>
class BST : public Dictionary<Key, Elem, KEComp, EEComp> {
private:
BinNode<Elem>* root; // Root of the BST
int nodecount; // Number of nodes in the BST
// Private "helper" functions
void clearhelp(BinNode<Elem>*);
BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
BinNode<Elem>* deletemin(BinNode<Elem>*, BinNode<Elem>*&);
BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,
BinNode<Elem>*&);
bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;
bool updatehelp(BinNode<Elem>*, const Key&, Elem&) const;
void inorderhelp(BinNode<Elem>*);
void preorderhelp(BinNode<Elem>*);
void postorderhelp(BinNode<Elem>*);
void printhelp(BinNode<Elem>*, int) const;
public:
BST() { root = NULL; nodecount = 0; } // Constructor
~BST() { clearhelp(root); } // Destructor
void clear()
{ clearhelp(root); root = NULL; nodecount = 0; }
bool insert(const Elem& e) {
root = inserthelp(root, e);
nodecount++;
return true;
}
bool remove(const Key& K, Elem& e) {
BinNode<Elem>* t = NULL;
root = removehelp(root, K, t);
if (t == NULL) return false; // Nothing found
e = t->val();
nodecount--;
delete t;
return true;
}
bool removeAny(Elem& e) { // Delete min value
if (root == NULL) return false; // Empty tree
BinNode<Elem>* t;
root = deletemin(root, t);
e = t->val();
delete t;
nodecount--;
return true;
}
bool find(const Key& K, Elem& e) const
{ return findhelp(root, K, e); }
int size() { return nodecount; }
void print() const {
if (root == NULL) cout << "The BST is empty.\n";
else printhelp(root, 0);
}
bool update(const Key& K, Elem& e)
{ return updatehelp(root, K, e); }
void inorder(){inorderhelp(root);}
void preorder(){preorderhelp(root);}
void postorder(){postorderhelp(root);}
};
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
clearhelp(BinNode<Elem>* subroot) {
if (subroot == NULL) return;
clearhelp(subroot->left());
clearhelp(subroot->right());
delete subroot;
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
inserthelp(BinNode<Elem>* subroot, const Elem& val) {
if (subroot == NULL) // Empty tree: create node
return (new BinNodePtr<Elem>(val, NULL, NULL));
if (EEComp::lt(val, subroot->val())) // Insert on left
subroot->setLeft(inserthelp(subroot->left(), val));
else subroot->setRight(inserthelp(subroot->right(), val));
return subroot; // Return subtree with node inserted
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
deletemin(BinNode<Elem>* subroot, BinNode<Elem>*& min) {
if (subroot->left() == NULL) { // Found min
min = subroot;
return subroot->right();
}
else { // Continue left
subroot->setLeft(deletemin(subroot->left(), min));
return subroot;
}
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
removehelp(BinNode<Elem>* subroot, const Key& K,
BinNode<Elem>*& t) {
if (subroot == NULL) return NULL; // Val is not in tree
else if (KEComp::lt(K, subroot->val())) // Check left
subroot->setLeft(removehelp(subroot->left(), K, t));
else if (KEComp::gt(K, subroot->val())) // Check right
subroot->setRight(removehelp(subroot->right(), K, t));
else { // Found it: remove it
BinNode<Elem>* temp;
t = subroot;
if (subroot->left() == NULL) // Only a right child
subroot = subroot->right(); // so point to right
else if (subroot->right() == NULL) // Only a left child
subroot = subroot->left(); // so point to left
else { // Both children are non-empty
subroot->setRight(deletemin(subroot->right(), temp));
Elem te = subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
t = temp;
}
}
return subroot;
}
template <class Key, class Elem, class KEComp, class EEComp>
bool BST<Key, Elem, KEComp, EEComp>:: findhelp(
BinNode<Elem>* subroot, const Key& K, Elem& e) const {
if (subroot == NULL) return false; // Empty tree
else if (KEComp::lt(K, subroot->val())) // Check left
return findhelp(subroot->left(), K, e);
else if (KEComp::gt(K, subroot->val())) // Check right
return findhelp(subroot->right(), K, e);
else { e = subroot->val(); return true; } // Found it
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
printhelp(BinNode<Elem>* subroot, int level) const {
if (subroot == NULL) return; // Empty tree
printhelp(subroot->left(), level+1); // Do left subtree
for (int i=0; i<level; i++) // Indent to level
cout << " ";
cout << subroot->val() <<"\n"; // Print node value
printhelp(subroot->right(), level+1); // Do right subtree
}
template <class Key, class Elem, class KEComp, class EEComp>
bool BST<Key, Elem, KEComp, EEComp>:: updatehelp(
BinNode<Elem>* subroot, const Key& K, Elem& e) const {
if (subroot == NULL) return false; // Empty tree
else if (KEComp::lt(K, subroot->val())) // Check left
return updatehelp(subroot->left(), K, e);
else if (KEComp::gt(K, subroot->val())) // Check right
return updatehelp(subroot->right(), K, e);
else { subroot->setVal(e); return true; } // Found it
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::inorderhelp(BinNode<Elem>* subroot)
{ if (subroot==NULL) return;
inorderhelp(subroot->left());
cout<<subroot->val()<<endl;
inorderhelp(subroot->right());
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::preorderhelp(BinNode<Elem>* subroot)
{ if (subroot==NULL) return;
cout<<subroot->val()<<endl;
preorderhelp(subroot->left());
preorderhelp(subroot->right());
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::postorderhelp(BinNode<Elem>* subroot)
{ if (subroot==NULL) return;
postorderhelp(subroot->left());
postorderhelp(subroot->right());
cout<<subroot->val()<<endl;
}
[/bs2.h]
// This file includes all of the pieces of the BST implementation
#include "dictionary.h"
#include "binnode.h"
// Binary Search Tree implementation for the Dictionary ADT
template <class Key, class Elem, class KEComp, class EEComp>
class BST : public Dictionary<Key, Elem, KEComp, EEComp> {
private:
BinNode<Elem>* root; // Root of the BST
int nodecount; // Number of nodes in the BST
// Private "helper" functions
void clearhelp(BinNode<Elem>*);
BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);
BinNode<Elem>* deletemin(BinNode<Elem>*, BinNode<Elem>*&);
BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,
BinNode<Elem>*&);
bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;
bool updatehelp(BinNode<Elem>*, const Key&, Elem&) const;
void inorderhelp(BinNode<Elem>*);
void preorderhelp(BinNode<Elem>*);
void postorderhelp(BinNode<Elem>*);
void printhelp(BinNode<Elem>*, int) const;
public:
BST() { root = NULL; nodecount = 0; } // Constructor
~BST() { clearhelp(root); } // Destructor
void clear()
{ clearhelp(root); root = NULL; nodecount = 0; }
bool insert(const Elem& e) {
root = inserthelp(root, e);
nodecount++;
return true;
}
bool remove(const Key& K, Elem& e) {
BinNode<Elem>* t = NULL;
root = removehelp(root, K, t);
if (t == NULL) return false; // Nothing found
e = t->val();
nodecount--;
delete t;
return true;
}
bool removeAny(Elem& e) { // Delete min value
if (root == NULL) return false; // Empty tree
BinNode<Elem>* t;
root = deletemin(root, t);
e = t->val();
delete t;
nodecount--;
return true;
}
bool find(const Key& K, Elem& e) const
{ return findhelp(root, K, e); }
int size() { return nodecount; }
void print() const {
if (root == NULL) cout << "The BST is empty.\n";
else printhelp(root, 0);
}
bool update(const Key& K, Elem& e)
{ return updatehelp(root, K, e); }
void inorder(){inorderhelp(root);}
void preorder(){preorderhelp(root);}
void postorder(){postorderhelp(root);}
};
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
clearhelp(BinNode<Elem>* subroot) {
if (subroot == NULL) return;
clearhelp(subroot->left());
clearhelp(subroot->right());
delete subroot;
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
inserthelp(BinNode<Elem>* subroot, const Elem& val) {
if (subroot == NULL) // Empty tree: create node
return (new BinNodePtr<Elem>(val, NULL, NULL));
if (EEComp::lt(val, subroot->val())) // Insert on left
subroot->setLeft(inserthelp(subroot->left(), val));
else subroot->setRight(inserthelp(subroot->right(), val));
return subroot; // Return subtree with node inserted
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
deletemin(BinNode<Elem>* subroot, BinNode<Elem>*& min) {
if (subroot->left() == NULL) { // Found min
min = subroot;
return subroot->right();
}
else { // Continue left
subroot->setLeft(deletemin(subroot->left(), min));
return subroot;
}
}
template <class Key, class Elem, class KEComp, class EEComp>
BinNode<Elem>* BST<Key, Elem, KEComp, EEComp>::
removehelp(BinNode<Elem>* subroot, const Key& K,
BinNode<Elem>*& t) {
if (subroot == NULL) return NULL; // Val is not in tree
else if (KEComp::lt(K, subroot->val())) // Check left
subroot->setLeft(removehelp(subroot->left(), K, t));
else if (KEComp::gt(K, subroot->val())) // Check right
subroot->setRight(removehelp(subroot->right(), K, t));
else { // Found it: remove it
BinNode<Elem>* temp;
t = subroot;
if (subroot->left() == NULL) // Only a right child
subroot = subroot->right(); // so point to right
else if (subroot->right() == NULL) // Only a left child
subroot = subroot->left(); // so point to left
else { // Both children are non-empty
subroot->setRight(deletemin(subroot->right(), temp));
Elem te = subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
t = temp;
}
}
return subroot;
}
template <class Key, class Elem, class KEComp, class EEComp>
bool BST<Key, Elem, KEComp, EEComp>:: findhelp(
BinNode<Elem>* subroot, const Key& K, Elem& e) const {
if (subroot == NULL) return false; // Empty tree
else if (KEComp::lt(K, subroot->val())) // Check left
return findhelp(subroot->left(), K, e);
else if (KEComp::gt(K, subroot->val())) // Check right
return findhelp(subroot->right(), K, e);
else { e = subroot->val(); return true; } // Found it
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::
printhelp(BinNode<Elem>* subroot, int level) const {
if (subroot == NULL) return; // Empty tree
printhelp(subroot->left(), level+1); // Do left subtree
for (int i=0; i<level; i++) // Indent to level
cout << " ";
cout << subroot->val() <<"\n"; // Print node value
printhelp(subroot->right(), level+1); // Do right subtree
}
template <class Key, class Elem, class KEComp, class EEComp>
bool BST<Key, Elem, KEComp, EEComp>:: updatehelp(
BinNode<Elem>* subroot, const Key& K, Elem& e) const {
if (subroot == NULL) return false; // Empty tree
else if (KEComp::lt(K, subroot->val())) // Check left
return updatehelp(subroot->left(), K, e);
else if (KEComp::gt(K, subroot->val())) // Check right
return updatehelp(subroot->right(), K, e);
else { subroot->setVal(e); return true; } // Found it
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::inorderhelp(BinNode<Elem>* subroot)
{ if (subroot==NULL) return;
inorderhelp(subroot->left());
cout<<subroot->val()<<endl;
inorderhelp(subroot->right());
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::preorderhelp(BinNode<Elem>* subroot)
{ if (subroot==NULL) return;
cout<<subroot->val()<<endl;
preorderhelp(subroot->left());
preorderhelp(subroot->right());
}
template <class Key, class Elem, class KEComp, class EEComp>
void BST<Key, Elem, KEComp, EEComp>::postorderhelp(BinNode<Elem>* subroot)
{ if (subroot==NULL) return;
postorderhelp(subroot->left());
postorderhelp(subroot->right());
cout<<subroot->val()<<endl;
}
[/bs2.h]
continuation...
[binnode]
// Binary tree node abstract class
template <class Elem>
class BinNode {
public:
// Return the node's element
virtual Elem& val() = 0;
// Set the node's element
virtual void setVal(const Elem&) = 0;
// Return the node's left child
virtual BinNode* left() const = 0;
// Set the node's left child
virtual void setLeft(BinNode*) = 0;
// Return the node's right child
virtual BinNode* right() const = 0;
// Set the node's right child
virtual void setRight(BinNode*) = 0;
// Return true iff the node is a leaf
virtual bool isLeaf() = 0;
};
// Binary tree node class
template <class Elem>
class BinNodePtr : public BinNode<Elem> {
private:
Elem it; // The node's value
BinNodePtr* lc; // Pointer to left child
BinNodePtr* rc; // Pointer to right child
public:
// Two constructors -- with and without initial values
BinNodePtr() { lc = rc = NULL; }
BinNodePtr(Elem e, BinNodePtr* l =NULL,
BinNodePtr* r =NULL)
{ it = e; lc = l; rc = r; }
~BinNodePtr() {} // Destructor
Elem& val() { return it; }
void setVal(const Elem& e) { it = e; }
inline BinNode<Elem>* left() const { return lc; }
void setLeft(BinNode<Elem>* b) { lc = (BinNodePtr*)b; } //conversion must be explicit
inline BinNode<Elem>* right() const { return rc; }
void setRight(BinNode<Elem>* b) { rc = (BinNodePtr*)b; }
bool isLeaf() { return (lc == NULL) && (rc == NULL); }
};
[/binnode]
[binnode]
// Binary tree node abstract class
template <class Elem>
class BinNode {
public:
// Return the node's element
virtual Elem& val() = 0;
// Set the node's element
virtual void setVal(const Elem&) = 0;
// Return the node's left child
virtual BinNode* left() const = 0;
// Set the node's left child
virtual void setLeft(BinNode*) = 0;
// Return the node's right child
virtual BinNode* right() const = 0;
// Set the node's right child
virtual void setRight(BinNode*) = 0;
// Return true iff the node is a leaf
virtual bool isLeaf() = 0;
};
// Binary tree node class
template <class Elem>
class BinNodePtr : public BinNode<Elem> {
private:
Elem it; // The node's value
BinNodePtr* lc; // Pointer to left child
BinNodePtr* rc; // Pointer to right child
public:
// Two constructors -- with and without initial values
BinNodePtr() { lc = rc = NULL; }
BinNodePtr(Elem e, BinNodePtr* l =NULL,
BinNodePtr* r =NULL)
{ it = e; lc = l; rc = r; }
~BinNodePtr() {} // Destructor
Elem& val() { return it; }
void setVal(const Elem& e) { it = e; }
inline BinNode<Elem>* left() const { return lc; }
void setLeft(BinNode<Elem>* b) { lc = (BinNodePtr*)b; } //conversion must be explicit
inline BinNode<Elem>* right() const { return rc; }
void setRight(BinNode<Elem>* b) { rc = (BinNodePtr*)b; }
bool isLeaf() { return (lc == NULL) && (rc == NULL); }
};
[/binnode]
Topic archived. No new replies allowed.