Hi,
I need to do this problem for an assignment. We have not focused very much on this topc and that would be great if someone could help me get started. I am not asking for a complete solution or anything, just to head me in the right direction. The problem is:
Problem: Specify, design, and implement a class for complete binary trees using the array representation. You should have only one member function that adds a nre node (since there is only one place where a node may be added), and one member function that removes the last node of the tree.
What I get is that complete binary tree should have all the leaves at the same depth. So basically we create a tree to which elemts can be added or removed through the user input. I am positng below source code for basic sturcture of a tree. I have not implemented any functions in it. If you can use the source below and guide me what I should do next. Thanks!
plusplus]
#include <cstdlib> //Provides EXIT_SUCCESS
#include <iostream> //Provides cout, cin
#include <string> //Provides string class
using namespace std;
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; }
//CONSTANT 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;
};
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr);
//Precondition: root_ptr is the root pointer of a binary tree (whihc 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 apointer to the root of this copy.
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr)
{
if (root_ptr != NULL)
{
tree_clear( root_ptr->left());
tree_clear( root_ptr->right());
delete root_ptr;
root_ptr = NULL;
}
}
template <class Item>
binary_tree_node<Item>* tree_copy
(const binary_tree_node<Item>* root_ptr)
{
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);
}
}