Question
Add a recursive function getHeight to the BinarySearchTree class in Exercise 1 that returns the height of the tree. Exercise 1 main.cpp #include stdafx.h #include
Add a recursive function getHeight to the BinarySearchTree class in Exercise 1 that returns the height of the tree.
Exercise 1
main.cpp
#include "stdafx.h" #include "BinarySearchTree.h" #include "time.h" #include
using namespace std;
int main() { BinarySearchTree bst;
int x;
if (bst.isEmpty()) cout << "BST is empty" << endl; else cout << "BST is not empty" << endl;
srand((unsigned int)time(0));
for (int i = 0; i < 10; i++) bst.add(rand() % 20);
if (bst.isEmpty()) cout << "BST is empty" << endl; else cout << "BST is not empty" << endl;
bst.display();
x = rand() % 20;
if (bst.search(x)) cout << x << " was found!" << endl; else cout << x << " was not found!" << endl;
cout << "Minimum of the tree = " << bst.getMinimum() << endl;
return 0; }
BinarySearchTree.h
#pragma once struct TreeNode { int info; //element stored in this node TreeNode *left; //link to left child TreeNode *right; //link to right child };
class BinarySearchTree { public: BinarySearchTree(); bool isEmpty(); void display(); bool search(int); void add(int); int getMinimum(); ~BinarySearchTree();
private: TreeNode* root;
void inorderDisplay(TreeNode*); bool search(int, TreeNode*); void add(int, TreeNode* &); TreeNode* getMinimum(TreeNode*); void deallocateMemory(TreeNode* &); };
BinarySearchTree.cpp
#include "stdafx.h" #include "BinarySearchTree.h" #include
BinarySearchTree::BinarySearchTree() { root = NULL; }
bool BinarySearchTree::isEmpty() { return root == NULL; }
void BinarySearchTree::display() { inorderDisplay(root); cout << endl; }
bool BinarySearchTree::search(int x) { return search(x, root); }
void BinarySearchTree::add(int x) { add(x, root); }
int BinarySearchTree::getMinimum() { return getMinimum(root)->info; }
BinarySearchTree::~BinarySearchTree() { deallocateMemory(root); }
void BinarySearchTree::inorderDisplay(TreeNode *p) { if (p != NULL) { inorderDisplay(p->left); cout << p->info << " "; inorderDisplay(p->right); } }
void BinarySearchTree::add(int x, TreeNode* & p) { if (p == NULL) { p = new TreeNode; p->info = x; p->left = p->right = NULL; } else { if (x <= p->info) add(x, p->left); else add(x, p->right); } }
bool BinarySearchTree::search(int x, TreeNode* p) { if (p == NULL) return false; else if (x == p->info) return true; else if (x < p->info) return search(x, p->left); else return search(x, p->right); }
TreeNode* BinarySearchTree::getMinimum(TreeNode* p) { if (p->left == NULL) return p; else return getMinimum(p->left); }
void BinarySearchTree::deallocateMemory(TreeNode* & p) { if (p != NULL) { deallocateMemory(p->left); deallocateMemory(p->right); delete p;
p = NULL; } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started