Using templates!

Change the existing code in intbst.h and intbst.cpp to accept any type of variable in the binary search tree (not just int).

intbst.h :

#ifndef INTBST_H
	#define INTBST_H
	#include
	using namespace std;
	class IntBST {
	public:
	// ctor, dtor, insert and one print method already done in intbst.cpp:
	IntBST(); // constructor
	~IntBST(); // destructor
	bool insert(int value); // insert value; return false if duplicate
	void printPreOrder() const; // prints tree data pre-order to cout
	void printInOrder() const; // print tree data in-order to cout
	void printPostOrder() const; // print tree data post-order to cout
	int sum() const; // sum of all values
	int count() const; // count of values
	bool contains(int value) const; // true if value is in tree
	int getPredecessor(int value) const; // returns the predecessor value of the given value or 0 if there is none
	int getSuccessor(int value) const; // returns the successor value of the given value or 0 if there is none
	bool remove(int value); // deletes the Node containing the given value from the tree
	private:
	struct Node {
	int info;
	Node *left, *right, * parent;
	// useful constructor:
	Node(int v=0) : info(v), left(0), right(0), parent(0) { }
	};
	// just one instance variable (pointer to root node):
	Node *root;
	// recursive utility functions for use by public methods above
	Node* getNodeFor(int value, Node* n) const; //returns the node for a given value or NULL if none exists
	void clear(Node *n); // for destructor
	bool insert(int value, Node *n); // note overloading names for simplicity
	void printPreOrder(Node *n) const;
	void printInOrder(Node *n) const;
	void printPostOrder(Node *n) const;
	int sum(Node *n) const;
	int count(Node *n) const;
	// these are used by getPredecessor and getSuccessor, and one of them used by remove
	Node* getSuccessorNode(int value) const; // returns the Node containing the successor of the given value
	Node* getPredecessorNode(int value) const; // returns the Node containing the predecessor of the given value
	};
	#endif intbst.cpp

intbst.cpp :

#include "intbst.h"
	#include
	using std::cout;
	// constructor sets up empty tree
	IntBST::IntBST() : root(0) { }
	// destructor deletes all nodes
	IntBST::~IntBST() {
	clear(root);
	}
	// recursive helper for destructor
	void IntBST::clear(Node *n) {
	if (n) {
	clear(n->left);
	clear(n->right);
	delete n;
	}
	}
	// insert value in tree; return false if duplicate
	bool IntBST::insert(int value) {
	// handle special case of empty tree first
	if (!root) {
	root = new Node(value);
	return true;
	}
	// otherwise use recursive helper
	return insert(value, root);
	}
	// recursive helper for insert (assumes n is never 0)
	bool IntBST::insert(int value, Node *n) {
	if (value == n->info)
	return false;
	if (value < n->info) {
	if (n->left)
	return insert(value, n->left);
	else {
	n->left = new Node(value);
	n->left->parent = n;
	return true;
	}
	}
	else {
	if (n->right)
	return insert(value, n->right);
	else {
	n->right = new Node(value);
	n->right->parent = n;
	return true;
	}
	}
	}
	// print tree data pre-order
	void IntBST::printPreOrder() const {
	printPreOrder(root);
	}
	// recursive helper for printPreOrder()
	void IntBST::printPreOrder(Node *n) const {
	if (n) {
	cout << n->info << " ";
	printPreOrder(n->left);
	printPreOrder(n->right);
	}
	}
	// print tree data in-order, with helper
	void IntBST::printInOrder() const {
	printInOrder(root);
	}
	void IntBST::printInOrder(Node *n) const {
	if (n) {
	printInOrder(n->left);
	cout<info<<" ";
	printInOrder(n->right);
	}
	}
	// prints tree data post-order, with helper
	void IntBST::printPostOrder() const {
	printPostOrder(root);
	}
	void IntBST::printPostOrder(Node *n) const {
	if (n) {
	printPostOrder(n->left);
	printPostOrder(n->right);
	cout << n->info << " ";
	}
	}
	// return sum of values in tree
	int IntBST::sum() const {
	return sum(root);
	}
	// recursive helper for sum
	int IntBST::sum(Node *n) const {
	if (n==NULL)
	return 0;
	return (sum(n->left)+sum(n->right)+n->info);
	}
	// return count of values
	int IntBST::count() const {
	return count(root);
	}
	// recursive helper for count
	int IntBST::count(Node *n) const {
	if(n==NULL)
	return 0;
	else{
	int c=1;
	c+=count(n->left);
	c+=count(n->right);
	return c;
	}
	}
	// Parameters:
	// int value: the value to be found
	IntBST::Node* IntBST::getNodeFor(int value, Node* n) const{
	/*while(n){
	if (n -> info == value)
	return n;
	if (n -> info > value)
	n = n -> left;
	if (n -> info < value)
	n = n -> right;
	//cout<info<
	}
	return NULL;*/
	if(n==NULL) return NULL;
	else if(n->info == value) return n;
	else if(n->info>value) return getNodeFor(value, n->left);
	else if(n->inforight);
	}
	// returns true if value is in the tree; false if not
	bool IntBST::contains(int value) const {
	return(getNodeFor(value, root)!=NULL);
	}
	// returns the Node containing the predecessor of the given value
	IntBST::Node* IntBST::getPredecessorNode(int value) const{
	Node* n = getNodeFor(value, root);
	if (n==NULL)
	return n;
	Node* temp = NULL;
	if(n->left){
	n=n->left;
	while(n->right){
	n = n->right;
	}
	temp = n;
	}
	else {
	while(n->parent){
	// Node* tempParent = n->parent;
	if(n->parent->info < value){
	temp=n->parent;
	break;
	}
	else{
	n = n->parent;
	}
	}
	}
	return temp;
	}
	// returns the predecessor value of the given value or 0 if there is none
	int IntBST::getPredecessor(int value) const{
	Node* val = getPredecessorNode(value);
	if (val == NULL){
	return 0;
	}
	else
	return val->info;
	}
	// returns the Node containing the successor of the given value
	IntBST::Node* IntBST::getSuccessorNode(int value) const{
	Node* n = getNodeFor(value, root);
	if (n==NULL){
	Node* n=NULL;
	return n;
	}
	Node* temp = NULL;
	if(n->right){
	n=n->right;
	while(n->left){
	n = n->left;
	}
	temp = n;
	}
	else {
	while(n->parent){
	// Node* tempParent = n->parent;
	if(n->parent->info > value){
	temp=n->parent;
	break;
	}
	else{
	n = n->parent;
	}
	}
	}
	return temp;
	}
	// returns the successor value of the given value or 0 if there is none
	int IntBST::getSuccessor(int value) const{
	Node* tmp = getSuccessorNode(value);
	if (tmp == NULL)
	return 0;
	else
	return (tmp->info);
	}
	// deletes the Node containing the given value from the tree
	// returns true if the node exist and was deleted or false if the node does not exist
	bool IntBST::remove(int value){
	if (!getNodeFor(value,root))
	return false;
	Node* n = getNodeFor(value, root);
	if (n->right==NULL && n->left==NULL){ //leaf
	if(n == root){
	root = NULL;
	delete n;
	}
	else if (n==(n->parent->left))
	n->parent->left = NULL;
	else
	n->parent->right = NULL;
	delete n;
	}
	else if(n->left == NULL || n->right == NULL){ //only one child
	if(n==root){ //and is root
	if(n->right) root = n->right;
	else root = n->left;
	}
	else{ //and is not root
	Node* next;
	if(n->right) next= n->right;
	else next = n->left;
	if(n->parent->right == n){ //if n is right of parent
	n->parent->right = next;
	n->parent->right->parent = n->parent;
	}
	else{ //else n is left of parent
	n->parent->left = next;
	n->parent->left->parent = n->parent;
	}
	}
	delete n;
	}
	else{ //two children
	Node* swap;
	int temp;
	swap = getPredecessorNode(n->info);
	temp = n->info;
	n->info = swap->info;
	swap->info = temp;
	remove(swap->info);
	}
	return true;
	}