Binary Tree Template Write your own version of a class template that will create
ID: 3670162 • Letter: B
Question
Binary Tree Template
Write your own version of a class template that will create a binary tree that can hold values of any data type. Demonstrate the class with a driver program. Place your binary tree template in it's own header file, Btree.h. Include methods for the following:
inserting new values into the tree
removing nodes from the tree
searching the tree
returning the number of nodes in the tree
displaying the contents of the tree using preorder traversal
Your public interface must include at least the following methods:
-- void insert( T )
-- void remove( T )
-- bool search( T )
-- void preprint()
-- int count()
Where T is a generic parameter ( you can name it anything, I just chose T )
Sample Usage:
BTree b;
b.preprint();
cout << b.count();
b.insert('A');
cout << b.search('A');
b.remove('A');
Should be able to write statements like this in a program and have your class compile and run.
The count method must use recursion, you may not store the number of nodes as an attribute within the class.
You may not use a container from the STL.
I've attached an incomplete BTree.h header file to get you started.
A sample run:
Could be anything that demonstrates the class. A menu-driven program would be great for this.
Perhaps include options for insert, remove, search, count, print operations:
(I)nsert
(R)emove
(S)earch
(C)ount
(P)rint
(Q)uit
In C++
Header File:
// complete these pre-processor directives
#ifndef
#define
#include <iostream>
using std::cout;
using std::endl;
template <class T>
class BTree
{
public:
// constructor
// destructor
// public interface prototypes
void insert( T );
void remove( T );
void preprint() const;
bool search( T value ) const
int count() const
private:
// define and declare the BTree node here
// recursive method prototypes
void preprint( Node* ) const;
};
// method definitions here
template< class T >
void BTree<T>::preprint( Node* r ) const
{
}
#endif
Explanation / Answer
Answer
//
// File: Btree.h
// Author: HARE KRISHNA
//
// Created on 21 February, 2016, 3:56 PM
//
#ifndef _BTREE_H
#define _BTREE_H
#endif /* _BTREE_H */
template<typename t>
class BinaryTree
{
public:
BinaryTree();
BinaryTree(T elements[], int arraySize);
BinaryTree(BinaryTree<T> &tree);
~BinaryTree();
bool search(T element) const;
virtual bool insert(T element);
virtual bool remove(T element);
void inorder() const;
void preorder() const;
void postorder() const;
int getSize() const;
void clear();
protected:
TreeNode<T> *root;
int size;
virtual TreeNode<T> * createNewNode(T element);
private:
void inorder(TreeNode<T> *root) const;
void postorder(TreeNode<T> *root) const;
void preorder(TreeNode<T> *root) const;
void copy(TreeNode<T> *root);
void clear(TreeNode<T> *root);
};
template <typename T>
BinaryTree<T>::BinaryTree()
{
root = NULL;
size = 0;
}
template <typename T>
BinaryTree<T>::BinaryTree(T elements[], int arraySize)
{
root = NULL;
size = 0;
for (int i = 0; i < arraySize; i++)
{
insert(elements[i]);
}
}
/* Copy constructor */
template <typename T>
BinaryTree<T>::BinaryTree(BinaryTree<T> &tree)
{
root = NULL;
size = 0;
copy(tree.root); // Recursively copy nodes to this tree
}
/* Copies the element from the specified tree to this tree */
template <typename T>
void BinaryTree<T>::copy(TreeNode<T> *root)
{
if (root != NULL)
{
insert(root->element);
copy(root->left);
copy(root->right);
}
}
/* Destructor */
template <typename T>
BinaryTree<T>::~BinaryTree()
{
clear();
}
/* Return true if the element is in the tree */
template <typename T>
bool BinaryTree<T>::search(T element) const
{
TreeNode<T> *current = root; // Start from the root
while (current != NULL)
if (element < current->element)
{
current = current->left; // Go left
}
else if (element > current->element)
{
current = current->right; // Go right
}
else // Element matches current.element
return true; // Element is found
return false; // Element is not in the tree
}
template <typename T>
TreeNode<T> * BinaryTree<T>::createNewNode(T element)
{
return new TreeNode<T>(element);
}
/* Insert element into the binary tree
* Return true if the element is inserted successfully
* Return false if the element is already in the list
*/
template <typename T>
bool BinaryTree<T>::insert(T element)
{
if (root == NULL)
root = createNewNode(element); // Create a new root
else
{
// Locate the parent node
TreeNode<T> *parent = NULL;
TreeNode<T> *current = root;
while (current != NULL)
if (element < current->element)
{
parent = current;
current = current->left;
}
else if (element > current->element)
{
parent = current;
current = current->right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (element < parent->element)
parent->left = createNewNode(element);
else
parent->right = createNewNode(element);
}
size++;
return true; // Element inserted
}
/* Inorder traversal */
template <typename T>
void BinaryTree<T>::inorder() const
{
inorder(root);
}
/* Inorder traversal from a subtree */
template <typename T>
void BinaryTree<T>::inorder(TreeNode<T> *root) const
{
if (root == NULL) return;
inorder(root->left);
cout << root->element << " ";
inorder(root->right);
}
/* Postorder traversal */
template <typename T>
void BinaryTree<T>::postorder() const
{
postorder(root);
}
/** Inorder traversal from a subtree */
template <typename T>
void BinaryTree<T>::postorder(TreeNode<T> *root) const
{
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->element << " ";
}
/* Preorder traversal */
template <typename T>
void BinaryTree<T>::preorder() const
{
preorder(root);
}
/* Preorder traversal from a subtree */
template <typename T>
void BinaryTree<T>::preorder(TreeNode<T> *root) const
{
if (root == NULL) return;
cout << root->element << " ";
preorder(root->left);
preorder(root->right);
}
/* Get the number of nodes in the tree */
template <typename T>
int BinaryTree<T>::getSize() const
{
return size;
}
/* Remove all nodes from the tree */
template <typename T>
void BinaryTree<T>::clear()
{
// Left as exercise
}
/* Return a path from the root leading to the specified element */
template <typename T>
vector<TreeNode<T>*> *BinaryTree<T>::path(T element) const
{
vector<TreeNode<T>* > *v = new vector<TreeNode<T>* >();
TreeNode<T> *current = root;
while (current != NULL)
{
v->push_back(current);
if (element < current->element)
current = current->left;
else if (element > current->element)
current = current->right;
else
break;
}
return v;
}
template <typename T>
bool BinaryTree<T>::remove(T element)
{
// Locate the node to be deleted and also locate its parent node
TreeNode<T> *parent = NULL;
TreeNode<T> *current = root;
while (current != NULL)
{
if (element < current->element)
{
parent = current;
current = current->left;
}
else if (element > current->element)
{
parent = current;
current = current->right;
}
else
break; // Element is in the tree pointed by current
}
if (current == NULL)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current->left == NULL)
{
// Connect the parent with the right child of the current node
if (parent == NULL)
{
root = current->right;
}
else
{
if (element < parent->element)
parent->left = current->right;
else
parent->right = current->right;
}
delete current; // Delete current
}
else
{
TreeNode<T> *parentOfRightMost = current;
TreeNode<T> *rightMost = current->left;
while (rightMost->right != NULL)
{
parentOfRightMost = rightMost;
rightMost = rightMost->right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current->element = rightMost->element;
// Eliminate rightmost node
if (parentOfRightMost->right == rightMost)
parentOfRightMost->right = rightMost->left;
else
// Special case: parentOfRightMost->right == current
parentOfRightMost->left = rightMost->left;
delete rightMost; // Delete rightMost
}
size--;
return true; // Element inserted
}
int main(){
BinaryTree<int> b ;
b.insert(45);
b.preorder();
b.postorder();
b.insert(76);
b.insert(98);
b.inorder();
b.insert(754);
b.insert(453);
BinaryTree<float> f ;
f.insert(374.5);
f.insert(53.6);
f.insert(43.1);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.