Binary Tree Template Write your own version of a class template that will create

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:

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<char> 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

Has to be in In C++ Pls

B Tree.h

Explanation / Answer

#include "BinarySearchTree.h" #include /** * Implements an unbalanced binary search tree. * Note that all "matching" is based on the left ); else if( t->element right ); else if( t->left != NULL && t->right != NULL ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { BinaryNode *oldNode = t; t = ( t->left != NULL ) ? t->left : t->right; delete oldNode; } } /** * Internal method to find the smallest item in a subtree t. * Return node containing the smallest item. */ template BinaryNode * BinarySearchTree::findMin( BinaryNode *t ) const { if( t == NULL ) return NULL; if( t->left == NULL ) return t; return findMin( t->left ); } /** * Internal method to find the largest item in a subtree t. * Return node containing the largest item. */ template BinaryNode * BinarySearchTree::findMax( BinaryNode *t ) const { if( t != NULL ) while( t->right != NULL ) t = t->right; return t; } /** * Internal method to find an item in a subtree. * x is item to search for. * t is the node that roots the tree. * Return node containing the matched item. */ template BinaryNode * BinarySearchTree:: find( const Comparable & x, BinaryNode *t ) const { if( t == NULL ) return NULL; else if( x element ) return find( x, t->left ); else if( t->element right ); else return t; // Match } /****** NONRECURSIVE VERSION************************* template BinaryNode * BinarySearchTree:: find( const Comparable & x, BinaryNode *t ) const { while( t != NULL ) if( x element ) t = t->left; else if( t->element right; else return t; // Match return NULL; // No match } *****************************************************/ /** * Internal method to make subtree empty. */ template void BinarySearchTree:: makeEmpty( BinaryNode * & t ) const { if( t != NULL ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = NULL; } /** * Internal method to print a subtree rooted at t in sorted order. */ template void BinarySearchTree::printTree( BinaryNode *t ) const { if( t != NULL ) { printTree( t->left ); cout left ), clone( t->right ) ); }

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.