Write a class For implementing a simple binary search tree capable of storing nu

Question

Write a class For implementing a simple binary search tree capable of storing numbers. The class should have member functions: void insert (double x) bool search(double x) void inorder (vector & v ) The insert function should not use recursion directly, or indirectly by calling a recursive function. The search function should work by calling a private recursive member function bool search (double x, BtreeNode *t) The inorder function is passed an initially empty vector v: it fills v with the inorder list of numbers stored in the binary search tree. Demonstrate the operation of the class using a suitable driver program.

Explanation / Answer

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

//Class declaration for Binary seach tree
class StringbinarysearchTree{
private:
class TreeNode{
friend class StringTree;
string str;
TreeNode *left;
TreeNode *right;
TreeNode(string s, TreeNode *l=NULL, TreeNode *r=NULL){
str=s, left=l, right=r;}
};
TreeNode *root;

void insertelement(TreeNode *&tree, string word);
void removeelement(TreeNode *&tree, string word);
void makeDeletionhere(TreeNode *&tree);
void destroySubtreehere(TreeNode *tree);
void displayInOrdertraversal(TreeNode *tree);
void displayPreOrdertraversal(TreeNode *tree);
void displayPostOrdertraversal(TreeNode *tree);


public:
//inline recursive functions
StringbinarysearchTree()
{root=NULL;}
~StringbinarysearchTree()
{destroySubtree(root);}

bool search(string word);
bool isBalanced(TreeNode *tree);
int height(TreeNode *tree);

void insertelement(string word)
{insertelement(root, word);}

void removeelement(string word)
{removeelement(root, word);}

void showInOrder(void)
{displayInOrdertraversal(root);}

void showPreOrder(void)
{displayPreOrder(root);}

void showPostOrder(void)
{displayPostOrdertraversal(root);}
void getTreeSize (int &size);
};

//This is used for inserting into the tree
void StringbinarysearchTree::insertelement(TreeNode *&tree, string word)
{
if(!tree)
{tree=new TreeNode(word);
return;}

if(tree->str.compare(word))
return;
if(tree->str.compare(word)<0)
insert(tree->left, word);
else
insert(tree->right, word);
}

//rThis function is used for removing from the tree
void StringbinarysearchTree::removeelement(TreeNode *&tree, string word)
{
if(!tree) return;
if(tree->str.compare(word)<0)
remove(tree->left, word);
else if(tree->str.compare(word)>0)
remove(tree->right, word);
else
makeDeletion(tree);
}
//This function is used for searching for data in the tree
bool StringbinarysearchTree::search(string word)
{
TreeNode *tree=root;
while(tree){
if(tree->str.compare(word))
return true;
else if(tree->str.compare(word)<0)
tree=tree->left;
else
tree=tree->right;
}
return false;
}
// destroys a subtree
void StringbinarysearchTree::destroySubtree(TreeNode *tree){
if(!tree) return;
destroySubtree(tree->left);
destroySubtree(tree->right);
delete tree;
}
//This functions prints using inorder method
void StringbinarysearchTree::displayInOrdertraversal(TreeNode *tree){
if(tree){
displayInOrder(tree->left);
cout<<tree->str<<" ";
displayInOrder(tree->right);
}
}
//This function prints using preorder method
void StringbinarysearchTree::displayPreOrdertraversal(TreeNode *tree){
if(tree){
cout<<tree->str<<" ";
displayPreOrder(tree->left);
displayPreOrder(tree->right);
}
}
//This functionprints using post order method
void StringbinarysearchTree::displayPostOrdertraversal(TreeNode *tree){
if(tree){
displayPostOrder(tree->left);
displayPostOrder(tree->right);
cout<<(tree->str)<<" ";
}
}
//for deleting
void StringbinarsearchTree::makeDeletionhere(TreeNode *&tree){
TreeNode *deleteNode;
TreeNode *attach;

if(!tree->right)
tree=tree->left;
else if(!tree->left)
tree=tree->right;
else
attach=tree->right;
while(attach->left)
{
attach=attach->left;
attach->left=tree->left;
tree=tree->right;
}
delete deleteNode;
}

void StringbinarysearchTree::getTreeSize (int &size)
{
TreeNode *tree=root;
while(tree){
if (tree->right)
{
size++;
tree=tree->right;
}
if (tree->left)
{
size++;
tree=tree->left;
}
}
}//end getTreeSize

bool StringTree::isBalanced(TreeNode *tree)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */

/* If tree is empty then return true */
if(!tree)
return 1;

/* Get the height of left and right sub trees */
lh = height(tree->left);
rh = height(tree->right);

if( abs(lh-rh) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right))
return 1;

/* If we reach here then tree is not balanced */
return 0;
}//end isBalanced

int StringTree::height(TreeNode *tree)
{
if (!tree)
return 0;
else
{
/* now we will be computing the depth of each subtree */
int lDepth = height(tree->left);
int rDepth = height(tree->right);

/* use the larger one */
if (lDepth > rDepth)
return (lDepth+1);
else return (rDepth+1);
}
}


}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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