In this lab you will implement a Binary Search Tree (BST). • The BST should be a

Question

In this lab you will implement a Binary Search Tree (BST).
• The BST should be able to hold a generic type. Use templates to help with that.
• You should provide a useful interface for the BST. The header file BST.h should look as follows:

#ifndef _BST_h
#define _BST_h
//includes if needed...

template <class T>
class Visitor;

template <class T>
class BSTNode {
public:
T data;
BSTNode<T> * left;
BSTNode<T> * right;

return true if this node is a leaf node.
bool isLeaf() const;

// return true if the tree is empty
bool isEmpty() const;

// Find a return node with data equal to ’el’ in
// this BSTNode. Return NULL if the node does
// not exist.
BSTNode<T> * find(const T & el) const;

//Insert element in the correct place under
// this BSTNode
BSTNode<T> * insert(const T & element);

// return the node with the minimum element under
// this BSTNode
BSTNode<T> * min() const;

// return the node with the maximum element under
// this BSTNode
BSTNode<T> * max() const;

// return the node that is next in order after
// this BSTNode
BSTNode<T> * next() const;

// return the node that is previous in order before
// this BSTNode
BSTNode<T> * prev() const;

// traverse the tree recursively starting from this node
// and go depth first. Call the visiotor ’v’ at every
// visited node exactly once.
void traverseRecD(Visitor<T> & v);

// traverse the tree in order.
// Call the visiotor ’v’ at every visited node exactly once.
void traverseInOrder(Visitor<T> & v);

// traverse the tree using a stack. Go depth first.

// Call the visiotor ’v’ at every visited node exactly once.
void traverseStackD(Visitor<T> & v);

// traverse the tree using a queue. Go breadth first.
// Call the visiotor ’v’ at every visited node exactly once.
void traverseQueueB(Visitor<T> & v);

};

#endif

• The BSTNode class defines a binary search tree. Your task is to implement the functions
declared in it. Some of the functions are already implemented for you. Inspect them carefully
before you start. You are allowed to add more functions and data members as needed.
– traverseRecD(..) is a recursive implementation of a Depth First Traversal (equivalent
to a pre-order traversal).
– traverseInOrder(..) is a recursive implementation of an an in-order traversal.
– traverseStackD(..) is a stack-based implementation of a Depth First Traversal.
– traverseQueueB(..) is a queue-based implementation of a Breadth First Traversal.
– insert(const T & element) inserts element in the appropriate place in the Tree and
returns a pointer to the modified tree which will be the tree itself in general or the newly
created Tree if it was a null object previously.
– min() returns a pointer to the node containing the smallest element in the tree.
– next(BSTnode * node) returns a pointer to the node containing the next larger element
in the Tree relative to the provided node.
– find (T & e) returns a pointer to the node containing the element e, or null if not
found.
• Notice that all traversal functions receive a function object of type Visitor defined in visitor.h

#ifndef _visits_h
#define _visits_h

#include <iostream>

using namespace std;
//includes if needed...

template <class T>
class Visitor {
public:
virtual bool operator() (BSTnode<T> * node)
{
//sample implementation, or any other implementation you propose
if (node!=NULL)
cout << " " << node->data;
else
cout << " null";
return true;
}
};
#endif

An object of type Visitor decides what to do once the traversal visits a node. In the above
implementation (which you can modify as you wish), it prints the data element to the standard
output. You can create a class that inherets from Visitor and provide another implementation
of operator()(..) and pass it as an argument to the traversal functions. The following is an
example of how you can call a function object of type Visitor on a BSTNode;

Visitor v;
BSTNode<int> *root = NULL;
root->insert(4);
v(root);
• To get you started, you are provided with the recursive implementation of Deapth first Search
Traversal and InOrder traversal which should be part of BST.cpp:

#include "BST.h"
#include "visitor.h"

using namespace std;

template<class T>
void BSTnode<T>::traverseRecD(Visitor<T> & v)
{
if (this!=NULL)
{
left->traverseRecD(v);
right->traverseRecD(v);
v.visit(this);
}
else
v.visit(NULL);
}

template<class T>
void BSTnode<T>::traverseInOrder(Visitor<T> & v)
{
if (this!=NULL)
{
left->traverseInOrder(v);
v.visit(this);
right->traverseInOrder(v);
}
else
v.visit(NULL);
}

Test your implementation with checkLab5.cpp. The checkLab5.cpp file contains the main(..)
function and it calls your code to build and test your binary search tree. Inspect it for insight on
how your code is expected to work.

checklab5.cpp:

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <cstring>

#include "BST.h"
#include "visitor.h"

using namespace std;

int
main(int argc, char** argv)
{

// you may want to try a sorted or a reverse sorted array
// to make sure your tree works fine
int a[] = {
5,4,6,3,7,2,8,1,9,12,13,98,76,12,0 };

const int n = sizeof(a)/sizeof(int);
BSTNode<int> * root = NULL;

for (int i = 0; i < n; i++){
root = root->insert(a[i]);
}

// check the minimum/next traversal
cout<< "Printing min/next:" << endl;
BSTNode<int> * node = root->min();
for (; node != NULL; node = node->next()){
cout << node->data << " ";
}
cout << endl;

// check the minimum/next traversal
cout<< "Printing max/prev:" << endl;
node = root->max();
for (; node != NULL; node = node->prev()){
cout << node->data << " ";
}

node = root->find(5);
cout << "Node containing 5 is: " << node << endl;

node = root->find(120);
cout << "Node containing 120 is: " << node << endl;

Visitor<int> v;

//traverse recursively depth first
cout<< "Traverse recursive depth first:" << endl;
root->traverseRecD(v);
cout<< endl;

//traverse in order
cout<< "Traverse in order:" << endl;
root->traverseInOrder(v);
cout<< endl;

//traverse depth first with a stack
cout<< "Traverse depth first with a stack:" << endl;
root->traverseStackD(v);
cout<< endl;

//traverse breadth first with a queue
cout<< "Traverse breadth first with a queue:" << endl;
root->traverseQueueB(v);
cout<< endl;

return 0;
}

Explanation / Answer

Dear, Giving complete code of binary search tree using template // Template TreeNode class definition. #ifndef TREENODE_H #define TREENODE_H // forward declaration of class Tree template class Tree; // TreeNode class-template definition template class TreeNode { friend class Tree; public: // constructor TreeNode( const NODETYPE &d ) : leftPtr( 0 ), // pointer to left subtree data( d ), // tree node data rightPtr( 0 ) // pointer to right substree { // empty body } // end TreeNode constructor // return copy of node's data NODETYPE getData() const { return data; } // end getData function private: TreeNode *leftPtr; // pointer to left subtree NODETYPE data; TreeNode *rightPtr; // pointer to right subtree }; // end class TreeNode #endif // Template Tree class definition. #ifndef TREE_H #define TREE_H #include #include #include "TreeNode.h" using namespace std; // Tree class-template definition template class Tree { public: Tree(); // constructor void insertNode( const NODETYPE & ); void preOrderTraversal() const; void inOrderTraversal() const; void postOrderTraversal() const; private: TreeNode *rootPtr; // utility functions void insertNodeHelper( TreeNode **, const NODETYPE & ); void preOrderHelper( TreeNode * ) const; void inOrderHelper( TreeNode * ) const; void postOrderHelper( TreeNode * ) const; }; // end class Tree // constructor template Tree::Tree() { rootPtr = 0; // indicate tree is initially empty } // end Tree constructor // insert node in Tree template void Tree::insertNode( const NODETYPE &value ) { insertNodeHelper( &rootPtr, value ); } // end function insertNode // utility function called by insertNode; receives a pointer // to a pointer so that the function can modify pointer's value template void Tree::insertNodeHelper( TreeNode **ptr, const NODETYPE &value ) { // subtree is empty; create new TreeNode containing value if ( *ptr == 0 ) *ptr = new TreeNode( value ); else // subtree is not empty { // data to insert is less than data in current node if ( value < ( *ptr )->data ) insertNodeHelper( &( ( *ptr )->leftPtr ), value ); else { // data to insert is greater than data in current node if ( value > ( *ptr )->data ) insertNodeHelper( &( ( *ptr )->rightPtr ), value ); else // duplicate data value ignored cout

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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