Assignment #3: Binary Search Trees Binary Search Tree Class Design the BinarySea
ID: 668817 • Letter: A
Question
Assignment #3: Binary Search Trees
Binary Search Tree Class
Design the BinarySearchTree class to create a binary tree that can hold values of integer data type. The class should have member functions for inserting, finding, deleting, Binary Search Tree Sort, displaying pre-, in-order, and post-order traversals. Also, implement the following functions.
bool has_14(TreeNode * root)
//Precondition: root is the root pointer of a binary tree (but
//NOT NECESSARILY a search tree).
//Post condition: The return value indicates whether 14 appears
//somewhere in the tree. NOTE: If the tree is empty, the function
//returns fals
int min(TreeNode * root)
//Pre-condition: root is the root pointer of a nonempty binary //search tree.
//Post-condition: The return value is the smallest value in the //tree.
Demonstrate the class with a driver program (myBST.cpp). You should use the specification file (BinarySearchTree.h) and driver program (myBST.cpp) without any modification.
/*
Header file for the BinarySearchTree class
*/
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include <iostream>
class BinarySearchTree
{
private:
struct TreeNode
{
int info;
TreeNode * left;
TreeNode * right;
};
public:
TreeNode * root;
BinarySearchTree();
~BinarySearchTree();
void insert(TreeNode *& tree, int item);
bool treeSearch(TreeNode *node, int key);
void deleteItem(TreeNode*& tree, int item);
void deleteNode(TreeNode *& tree);
void getPredecessor(TreeNode* tree, int& item);
void preOrder(TreeNode *tree);
void inOrder(TreeNode *tree);
void postOrder(TreeNode *tree);
bool empty() const;
bool has_14(TreeNode *root);
int min(TreeNode * root);
void BSTsort(TreeNode* tree);
};
#endif
#include <iostream>
#include "BinarySearchTree.h"
using namespace std;
int main()
{
//create an instance of BinarySearchTree
BinarySearchTree myBST;
//insert the values
cout << "Inserting nodes 7, 3, 10, 1, 6, 14, 4, 7, 13 sequentially ";
myBST.insert(myBST.root, 7);
myBST.insert(myBST.root, 3);
myBST.insert(myBST.root, 10);
myBST.insert(myBST.root, 1);
myBST.insert(myBST.root, 6);
myBST.insert(myBST.root, 14);
myBST.insert(myBST.root, 4);
myBST.insert(myBST.root, 7);
myBST.insert(myBST.root, 13);
//print the tree in order
cout << "Here are the values in the tree (in-order traversal): ";
myBST.inOrder(myBST.root);
//print the tree pre order
cout << " Here are the values in the tree (pre-order traversal): ";
myBST.preOrder(myBST.root);
//print the tree post order
cout << " Here are the values in the tree (post-order traversal): ";
myBST.postOrder(myBST.root);
//deleting 6
cout << " Deleting 6... ";
myBST.deleteItem(myBST.root, 6);
//deleting 13
cout << "Deleting 13... ";
myBST.deleteItem(myBST.root, 13);
//print the tree in order
cout << " Now, here are the nodes (in order traversal): ";
myBST.inOrder(myBST.root);
cout << endl << endl;
//search for 14
if (myBST.has_14(myBST.root))
cout << " Yes, 14 is in the binary tree ";
else
cout << " No, 14 is not in the tree ";
//find and print the min
int minValue = myBST.min(myBST.root);
cout << "The minimum value in the tree is " << minValue << endl << endl;
//BST sort
myBST.insert(myBST.root, 6);
myBST.insert(myBST.root, 13);
cout << "BST Sort: The result of BST Sort for node values is: ";
myBST.BSTsort(myBST.root);
cout << endl;
system("pause");
return 0;
}
Explanation / Answer
/*
* BinarySearchTree.h
*
* Created on: 16-Sep-2015
* Author: Ravi
*/
/*
Header file for the BinarySearchTree class
*/
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include <iostream>
class BinarySearchTree {
private:
struct TreeNode
{
int info;
TreeNode * left;
TreeNode * right;
};
void search(TreeNode *node, int key, TreeNode* searchNode);
public:
TreeNode * root ;
BinarySearchTree();
~BinarySearchTree();
void insert(TreeNode *& tree, int item);
bool treeSearch(TreeNode *node, int key);
void deleteItem(TreeNode*& tree, int item);
void deleteNode(TreeNode *& tree);
void getPredecessor(TreeNode* tree, int& item);
void preOrder(TreeNode *tree);
void inOrder(TreeNode *tree);
void postOrder(TreeNode *tree);
bool empty() const;
bool has_14(TreeNode *root);
int min(TreeNode * root);
void BSTsort(TreeNode* tree);
};
#endif /* BINARYSEARCHTREE_H_ */
/*
* BinarySearchTree.cpp
*
* Created on: 16-Sep-2015
* Author: Ravi
*/
#include "BinarySearchTree.h"
using namespace std;
BinarySearchTree::BinarySearchTree() {
// TODO Auto-generated constructor stub
root = NULL;
}
BinarySearchTree::~BinarySearchTree() {
// TODO Auto-generated destructor stub
}
void BinarySearchTree::insert(TreeNode*& tree, int item) {
TreeNode * newNode = new TreeNode;
newNode->info = item;
newNode->left = NULL;
newNode->right = NULL;
if (root == NULL)
{
root = newNode;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == item)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > item)
{
if (tree->left != NULL)
{
insert(tree->left, item);
}
else
{
tree->left = newNode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, item);
}
else
{
tree->right = newNode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
void BinarySearchTree::inOrder(TreeNode* tree) {
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (tree != NULL)
{
inOrder(tree->left);
cout<<tree->info<<" ";
inOrder(tree->right);
}
}
void BinarySearchTree::preOrder(TreeNode* tree) {
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (tree != NULL)
{
cout<<tree->info<<" ";
preOrder(tree->left);
preOrder(tree->right);
}
}
void BinarySearchTree::postOrder(TreeNode* tree) {
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (tree != NULL)
{
postOrder(tree->left);
postOrder(tree->right);
cout<<tree->info<<" ";
}
}
bool BinarySearchTree::treeSearch(TreeNode* node, int key) {
TreeNode* searchNode = new TreeNode;
searchNode-> info = -11111;
search(node, key, searchNode);
if(searchNode->info == key) {
cout << "Item found : " << key <<endl;
} else
cout << "Item Not found : "<< key <<endl;
return searchNode->info == key;
}
void BinarySearchTree::search(TreeNode *node, int key, TreeNode* searchNode) {
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (node != NULL)
{
if(node->info == key) {
searchNode->info = node->info;
searchNode->left = node->left;
searchNode->right = node->right;
return;
}
else {
search(node->left, key, searchNode);
search(node->right, key, searchNode);
}
}
}
bool BinarySearchTree::has_14(TreeNode* root) {
return treeSearch(root, 14);
}
/*
void BinarySearchTree::deleteItem(TreeNode*& tree, int item) {
}
void BinarySearchTree::getPredecessor(TreeNode* tree, int& item) {
}
bool BinarySearchTree::empty() const {
}
bool BinarySearchTree::has_14(TreeNode* root) {
}
int BinarySearchTree::min(TreeNode* root) {
}
void BinarySearchTree::BSTsort(TreeNode* tree) {
}
*/
#include <iostream>
#include "BinarySearchTree.h"
using namespace std;
#include<stdio.h>
int main()
{
//create an instance of BinarySearchTree
BinarySearchTree myBST;
//insert the values
cout << "Inserting nodes 7, 3, 10, 1, 6, 14, 4, 7, 13 sequentially ";
myBST.insert(myBST.root, 7);
myBST.insert(myBST.root, 3);
myBST.insert(myBST.root, 10);
myBST.insert(myBST.root, 1);
myBST.insert(myBST.root, 6);
myBST.insert(myBST.root, 14);
myBST.insert(myBST.root, 4);
myBST.insert(myBST.root, 7);
myBST.insert(myBST.root, 13);
//print the tree in order
//print the tree in order
cout << "Here are the values in the tree (in-order traversal): ";
myBST.inOrder(myBST.root);
//print the tree pre order
cout << " Here are the values in the tree (pre-order traversal): ";
myBST.preOrder(myBST.root);
//print the tree post order
cout << " Here are the values in the tree (post-order traversal): " << endl;
myBST.postOrder(myBST.root);
cout << " searching tree for node 7" << endl;
bool found = myBST.treeSearch(myBST.root, 7);
cout << "Found the node: "<< (found ==1 ? "True" : "false")<<endl;
return 0;
}