Please Need help with Data Structures C++ lab. Need help writing the main.cpp fo
ID: 3862705 • Letter: P
Question
Please Need help with Data Structures C++ lab.
Need help writing the main.cpp for the problem.
The objective of this problem is to tree implementations concepts in C++.
Specifically, the exercise is to do the problem below. Use the bintree.h and bintree.template files provided.
// FILE: bintree.h (part of the namespace main_savitch_10)
// PROVIDES: A template class for a node in a binary tree and functions for
// manipulating binary trees. The template parameter is the type of data in
// each node.
//
// TYPEDEF for the binary_tree_node<Item> template class:
// Each node of the tree contains a piece of data and pointers to its
// children. The type of the data (binary_tree_node<Item>::value_type) is
// the Item type from the template parameter. The type may be any of the C++
// built-in types (int, char, etc.), or a class with a default constructor,
// and an assignment operator.
//
// CONSTRUCTOR for the binary_tree_node<Item> class:
// binary_tree_node(
// const item& init_data = Item( ),
// binary_tree_node<Item>* init_left = NULL,
// binary_tree_node<Item>* init_right = NULL
// )
// Postcondition: The new node has its data equal to init_data,
// and it's child pointers equal to init_left and init_right.
//
// MEMBER FUNCTIONS for the binary_tree_node<Item> class:
// const item& data( ) const <----- const version
// and
// Item& data( ) <----- non-const version
// Postcondition: The return value is a reference to the data from
// this binary_tree_node.
//
// const binary_tree_node* left( ) const <----- const version
// and
// binary_tree_node* left( ) <----- non-const version
// and
// const binary_tree_node* right( ) const <----- const version
// and
// binary_tree_node* right( ) <----- non-const version
// Postcondition: The return value is a pointer to the left or right child
// (which will be NULL if there is no child).
//
// void set_data(const Item& new_data)
// Postcondition: The binary_tree_node now contains the specified new data.
//
// void set_left(binary_tree_node* new_link)
// and
// void set_right(binary_tree_node* new_link)
// Postcondition: The binary_tree_node now contains the specified new link
// to a child.
//
// bool is_leaf( )
// Postcondition: The return value is true if the node is a leaf;
// otherwise the return value is false.
//
// NON-MEMBER FUNCTIONS to maniplulate binary tree nodes:
// tempate <class Process, class BTNode>
// void inorder(Process f, BTNode* node_ptr)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree).
// Postcondition: If node_ptr is non-NULL, then the function f has been
// applied to the contents of *node_ptr and all of its descendants, using
// an in-order traversal.
// Note: BTNode may be a binary_tree_node or a const binary tree node.
// Process is the type of a function f that may be called with a single
// Item argument (using the Item type from the node).
//
// tempate <class Process, class BTNode>
// void postorder(Process f, BTNode* node_ptr)
// Same as the in-order function, except with a post-order traversal.
//
// tempate <class Process, class BTNode>
// void preorder(Process f, BTNode* node_ptr)
// Same as the in-order function, except with a pre-order traversal.
//
// template <class Item, class SizeType>
// void print(const binary_tree_node<Item>* node_ptr, SizeType depth)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree). If the pointer is
// not NULL, then depth is the depth of the node pointed to by node_ptr.
// Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr
// and all its descendants have been written to cout with the << operator,
// using a backward in-order traversal. Each node is indented four times
// its depth.
//
// template <class Item>
// void tree_clear(binary_tree_node<Item>*& root_ptr)
// Precondition: root_ptr is the root pointer of a binary tree (which may
// be NULL for the empty tree).
// Postcondition: All nodes at the root or below have been returned to the
// heap, and root_ptr has been set to NULL.
//
// template <class Item>
// binary_tree_node<Item>* tree_copy(const binary_tree_node<Item>* root_ptr)
// Precondition: root_ptr is the root pointer of a binary tree (which may
// be NULL for the empty tree).
// Postcondition: A copy of the binary tree has been made, and the return
// value is a pointer to the root of this copy.
//
// template <class Item>
// size_t tree_size(const binary_tree_node<Item>* node_ptr)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree).
// Postcondition: The return value is the number of nodes in the tree.
#ifndef BINTREE_H
#define BINTREE_H
#include <cstdlib> // Provides NULL and size_t
namespace main_savitch_10
{
template <class Item>
class binary_tree_node
{
public:
// TYPEDEF
typedef Item value_type;
// CONSTRUCTOR
binary_tree_node(
const Item& init_data = Item( ),
binary_tree_node* init_left = NULL,
binary_tree_node* init_right = NULL
)
{
data_field = init_data;
left_field = init_left;
right_field = init_right;
}
// MODIFICATION MEMBER FUNCTIONS
Item& data( ) { return data_field; }
binary_tree_node* left( ) { return left_field; }
binary_tree_node* right( ) { return right_field; }
void set_data(const Item& new_data) { data_field = new_data; }
void set_left(binary_tree_node* new_left) { left_field = new_left; }
void set_right(binary_tree_node* new_right) { right_field = new_right; }
// CONST MEMBER FUNCTIONS
const Item& data( ) const { return data_field; }
const binary_tree_node* left( ) const { return left_field; }
const binary_tree_node* right( ) const { return right_field; }
bool is_leaf( ) const
{ return (left_field == NULL) && (right_field == NULL); }
private:
Item data_field;
binary_tree_node *left_field;
binary_tree_node *right_field;
};
// NON-MEMBER FUNCTIONS for the binary_tree_node<Item>:
template <class Process, class BTNode>
void inorder(Process f, BTNode* node_ptr);
template <class Process, class BTNode>
void preorder(Process f, BTNode* node_ptr);
template <class Process, class BTNode>
void postorder(Process f, BTNode* node_ptr);
template <class Item, class SizeType>
void print(binary_tree_node<Item>* node_ptr, SizeType depth);
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr);
template <class Item>
binary_tree_node<Item>* tree_copy(const binary_tree_node<Item>* root_ptr);
template <class Item>
std::size_t tree_size(const binary_tree_node<Item>* node_ptr);
}
#include "bintree.template"
#endif
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// FILE: bintree.template
// IMPLEMENTS: The binary_tree node class (see bintree.h for documentation).
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL, std::size_t
#include <iomanip> // Provides std::setw
#include <iostream> // Provides std::cout
namespace main_savitch_10
{
template <class Process, class BTNode>
void inorder(Process f, BTNode* node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL)
{
inorder(f, node_ptr->left( ));
f( node_ptr->data( ) );
inorder(f, node_ptr->right( ));
}
}
template <class Process, class BTNode>
void postorder(Process f, BTNode* node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL)
{
postorder(f, node_ptr->left( ));
postorder(f, node_ptr->right( ));
f(node_ptr->data( ));
}
}
template <class Process, class BTNode>
void preorder(Process f, BTNode* node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL)
{
f( node_ptr->data( ) );
preorder(f, node_ptr->left( ));
preorder(f, node_ptr->right( ));
}
}
template <class Item, class SizeType>
void print(binary_tree_node<Item>* node_ptr, SizeType depth)
// Library facilities used: iomanip, iostream, stdlib
{
if (node_ptr != NULL)
{
print(node_ptr->right( ), depth+1);
std::cout << std::setw(4*depth) << ""; // Indent 4*depth spaces.
std::cout << node_ptr->data( ) << std::endl;
print(node_ptr->left( ), depth+1);
}
}
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr)
// Library facilities used: cstdlib
{
binary_tree_node<Item>* child;
if (root_ptr != NULL)
{
child = root_ptr->left( );
tree_clear( child );
child = root_ptr->right( );
tree_clear( child );
delete root_ptr;
root_ptr = NULL;
}
}
template <class Item>
binary_tree_node<Item>* tree_copy(const binary_tree_node<Item>* root_ptr)
// Library facilities used: cstdlib
{
binary_tree_node<Item> *l_ptr;
binary_tree_node<Item> *r_ptr;
if (root_ptr == NULL)
return NULL;
else
{
l_ptr = tree_copy( root_ptr->left( ) );
r_ptr = tree_copy( root_ptr->right( ) );
return
new binary_tree_node<Item>( root_ptr->data( ), l_ptr, r_ptr);
}
}
template <class Item>
size_t tree_size(const binary_tree_node<Item>* node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr == NULL)
return 0;
else
return
1 + tree_size(node_ptr->left( )) + tree_size(node_ptr->right( ));
}
}
Explanation / Answer
Answer:
# include <iostream>
# include <cstdlib>
using namespace std;
struct node
{
int value;
struct node *first;
struct node *second;
}*root;
class BST
{
public:
void search(int, node **, node **);
void push(int);
void del(int);
void function_one(node *,node *);
void function_two(node *,node *);
void function_three(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
int main()
{
int option, num;
BST bst;
node *value;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.push Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Inorder Traversal"<<endl;
cout<<"4.Preorder Traversal"<<endl;
cout<<"5.Postorder Traversal"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter your option : ";
cin>>option;
switch(option)
{
case 1:
value = new node;
cout<<"Enter the number to be pushed : ";
cin>>value->value;
bst.push(root, value);
case 2:
if (root == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>num;
bst.del(num);
break;
case 3:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong option"<<endl;
}
}
}
void BST::search(int input, node **pointer, node **places)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*places = NULL;
*pointer = NULL;
return;
}
if (input == root->value)
{
*places = root;
*pointer = NULL;
return;
}
if (input < root->value)
ptr = root->first;
else
ptr = root->second;
ptrsave = root;
while (ptr != NULL)
{
if (input == ptr->value)
{
*places = ptr;
*pointer = ptrsave;
return;
}
ptrsave = ptr;
if (input < ptr->value)
ptr = ptr->first;
else
ptr = ptr->second;
}
*places = NULL;
*pointer = ptrsave;
}
void BST::push(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->value = newnode->value;
root->first = NULL;
root->second = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->value == newnode->value)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->value > newnode->value)
{
if (tree->first != NULL)
{
push(tree->first, newnode);
}
else
{
tree->first = newnode;
(tree->first)->first = NULL;
(tree->first)->second = NULL;
cout<<"Node Added To first"<<endl;
return;
}
}
else
{
if (tree->second != NULL)
{
push(tree->second, newnode);
}
else
{
tree->second = newnode;
(tree->second)->first = NULL;
(tree->second)->second = NULL;
cout<<"Node Added To second"<<endl;
return;
}
}
}
void BST::del(int input)
{
node *pointerent, *place;
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
search(input, &pointerent, &place);
if (place == NULL)
{
cout<<"input not present in tree"<<endl;
return;
}
if (place->first == NULL && place->second == NULL)
function_one(pointerent, place);
if (place->first != NULL && place->second == NULL)
function_two(pointerent, place);
if (place->first == NULL && place->second != NULL)
function_two(pointerent, place);
if (place->first != NULL && place->second != NULL)
function_three(pointerent, place);
free(place);
}
void BST::function_one(node *pointer, node *places )
{
if (pointer == NULL)
{
root = NULL;
}
else
{
if (places == pointer->first)
pointer->first = NULL;
else
pointer->second = NULL;
}
}
void BST::function_two(node *pointer, node *places)
{
node *child;
if (places->first != NULL)
child = places->first;
else
child = places->second;
if (pointer == NULL)
{
root = child;
}
else
{
if (places == pointer->first)
pointer->first = child;
else
pointer->second = child;
}
}
void BST::function_three(node *pointer, node *places)
{
node *ptr, *ptrsave, *suc, *pointersuc;
ptrsave = places;
ptr = places->second;
while (ptr->first != NULL)
{
ptrsave = ptr;
ptr = ptr->first;
}
suc = ptr;
pointersuc = ptrsave;
if (suc->first == NULL && suc->second == NULL)
function_one(pointersuc, suc);
else
function_two(pointersuc, suc);
if (pointer == NULL)
{
root = suc;
}
else
{
if (places == pointer->first)
pointer->first = suc;
else
pointer->second = suc;
}
suc->first = places->first;
suc->second = places->second;
}
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->value<<" ";
preorder(ptr->first);
preorder(ptr->second);
}
}
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->first);
cout<<ptr->value<<" ";
inorder(ptr->second);
}
}
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->first);
postorder(ptr->second);
cout<<ptr->value<<" ";
}
}
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->second, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->value;
display(ptr->first, level+1);
}
}