Binary Search Tree is a data structure that holds a list of items with a tree st
ID: 3694954 • Letter: B
Question
Binary Search Tree is a data structure that holds a list of items with a tree structure, which has the following feature: the left child is always smaller than the parent; while the right child is greater than or equal to the parent. In this homework, you need to implement all functions in the defined Binary Search Tree (BSTree) class (prototype is provided by the instructor). Please download the header file (BSTree.h) from ecourses, read the comments and complete them using C++. You need to implement all of the BSTree ADT functions in BSTree.cpp file, and test them in main.cpp. #ifndef BSTREE_H #define BSTREE_H template class TreeNode { public: TreeNode(DataType newData, TreeNode* LEFT, TreeNode* RIGHT); DataType info; TreeNode* left; TreeNode* right; }; template class BSTree { public: BSTree(); ~BSTree(); bool isEmpty() const; bool isFull() const; int NumofNodes() const; void makeEmpty(); void clearHelper(TreeNode* node); void insertItem(DataType newItem); void insertHelper(TreeNode *&node, DataType& newItem); bool deleteItem(DataType& item); bool deleteHelper(TreeNode *&node, DataType& item); TreeNode* retrieveItem(DataType& item); TreeNode* retrieveHelper(TreeNode *node, DataType& newItem); void print() const; void print_inorder(TreeNode* node) const; void print_preorder(TreeNode* node) const; void print_postorder(TreeNode* node) const; void showStructure() const; void showHelper(TreeNode *p, int level) const; int getHeight() const; int getHeightHelper(TreeNode *p) const; private: TreeNode* root; int numofNodes; }; #endif #include #include "tree.h" using namespace std; int main() { BSTree myTree; myTree.insertItem('K'); myTree.insertItem('D'); myTree.insertItem('M'); myTree.insertItem('C'); myTree.insertItem('F'); myTree.insertItem('B'); myTree.insertItem('A'); myTree.insertItem('P'); myTree.showStructure(); cout << "The height is: " << myTree.getHeight() << endl; myTree.deleteItem('A'); myTree.showStructure(); cout << "The height is: " << myTree.getHeight() << endl; myTree.makeEmpty(); return 0; }
Explanation / Answer
//
// File: BSTREE.h
// Author: RAM
//
// Created on 27 April, 2016, 10:37 PM
//
#ifndef _BSTREE_H
#define _BSTREE_H
#endif /* _BSTREE_H */
template class TreeNode {
public:
TreeNode(DataType newData,
TreeNode* LEFT, TreeNode* RIGHT);
DataType info;
TreeNode* left;
TreeNode* right;
};
template class BSTree {
public:
BSTree();
~BSTree();
bool isEmpty() const;
bool isFull() const;
int NumofNodes() const;
void makeEmpty();
void clearHelper(TreeNode* node);
void insertItem(DataType newItem);
void insertHelper(TreeNode *&node, DataType& newItem);
bool deleteItem(DataType& item);
bool deleteHelper(TreeNode *&node, DataType& item);
TreeNode* retrieveItem(DataType& item);
TreeNode* retrieveHelper(TreeNode *node, DataType& newItem);
void print() const;
void print_inorder(TreeNode* node) const;
void print_preorder(TreeNode* node) const;
void print_postorder(TreeNode* node) const;
void showStructure() const;
void showHelper(TreeNode *p, int level) const;
int getHeight() const;
int getHeightHelper(TreeNode *p) const;
private:
TreeNode* root;
int numofNodes;
};
template<class T>
void BSTree<T>::print_inorder(TreeNode* p)const
{
if(p != NULL)
{
if(p->left) print_inorder(p->left);
cout<<" "<<p->info<<" ";
if(p->right) print_inorder(p->right);
}
else return;
}
template<class T>
void BSTree<T>::print_postorder(TreeNode* p)const
{
if(p != NULL)
{
if(p->left) print_postorder(p->left);
if(p->right) print_postorder(p->right);
cout<<" "<<p->info<<" ";
}
else return;
}
template<class T>
void BSTree<T>::print_inorder(TreeNode* p)const
{
if(p != NULL)
{
if(p->left) print_inorder(p->left);
cout<<" "<<p->info<<" ";
if(p->right) print_inorder(p->right);
}
else return;
}
using namespace std;
int main()
{
BSTree myTree;
myTree.insertItem('K');
myTree.insertItem('D');
myTree.insertItem('M');
myTree.insertItem('C');
myTree.insertItem('F');
myTree.insertItem('B');
myTree.insertItem('A');
myTree.insertItem('P');
myTree.showStructure();
cout << "The height is: " << myTree.getHeight() << endl;
myTree.deleteItem('A');
myTree.showStructure(); cout << "The height is: " <<
myTree.getHeight() << endl;
myTree.makeEmpty();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.