Binary Tree Template Write your own version of a class template that will create
ID: 3674369 • 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++ pls
// 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
#include <iostream>
Template <T>
Class Btree
{
Public:
Struct tree
{
T data;
Struct tree * left;
Struct tree*right;
};
Typedef Struct tree node;
Void main()
{
node * root=NULL;
Clrscr();
Void insert(node*, T data);
Void remove(node*);
Void preprint(node*);const
bool search (node*);const
Int count()const
}
};
Template<classT>
Void Btree<T>::insert(node*,Tdata)
Int v,t,f=0;
Node*p=NULL,*c,*temp;
C=t;
temp->data=v;
temp->left=NULL;
temp->right=NULL;
if(t==NULL)
t=temp;
else
{
While (c|=NULL)
{
P=c;
If(temp->data < c->data)
{
F=1;
C=c->left;
}
Else if(temp->data > c->data)
{
F=0;
C=c->right;
}
}
If (f==1)
p->left=temp;
else
p->right=temp;
}
Return(t);
}
Template class<T>
Void Btree<T>::Void print(node*)
{
Void inorder(node *t)
{
If(t==NULL)
Return(t);
Inorder (t->left);
Cout<< t->data;
Inorder (t->right);
}
Void Preorder (node*t)
{
If (t==NULL)
Return(t);
Cout<< t->data;
Preorder (t->left);
Preorder (t->right);
}
Void postorder (node*t)
{
If (t==NULL)
Return (t);
Postorder(t->left);
Postorder(t->right);
Cout<<t->data;
}
}
Template<class T>
Void btree <T>::void search(node*)
{
Int n;
While(t)
{
n=t->data;
t=t->left;
cout<< n;
else
t=t->data;
cout<< n;
}
}
Template <class T>
Void Btree<T>::void remove(node*)
{
Static int c=0;
If(t==NULL)
Return ( c);
C=remove (t->left);
If (t->left==NULL && t->right==NULL)
C++;
C=remove(t->right);
}
Template <class T>
Void Btree<T>::int Count(node *t)
{
Static int c=0;
If (t==NULL)
return ( c );
c=count (t->left);
c++;
c=count (t->right);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.