Binary Tree help!

[johnnygaddar]

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);
    }
}

[Narue]

>If you can use the source below and guide me what I should do next.
Basically you haven't done anything, but you seem to understand the problem well enough. What you need to do is figure out how to add a new node at the correct position (as far to the right as possible on the first non-empty level without leaving gaps). I'll even give you three hints to start you thinking:

1) Think in terms of traversals and see if you can figure out an algorithm for finding the "last" node in a complete tree. From there it isn't difficult to see how you can add a new node. If the "last" node is also the last node on the level, start a new level (from the root, go left all the way and add a new node at the end of the path). If it isn't the last node on the level, find the inorder successor and add a new inorder node. Note that this isn't a good solution. It's very brute forcey and naive.

2) A complete binary tree is very well suited to storage in an array. Do some research on heaps, because they take advantage of that, and so can you.

3) The mathematical properties of a complete tree are very uniform. It's not hard to figure out, in a complete tree of N nodes, the physical location of the "last" node. Likewise, you can easily figure out mathematically where the physical location of the parent of the next "last" node to be inserted is (the kth node). Using that you can perform a simple traversal, halt when you get to the kth node and insert your new "last" node. This is an elegant solution.

[johnnygaddar]

thanks Narue!

i am using array method as we r suppoed to. so basically the program deletes the node of the tree which is the last elemt of the array. right?