Array based Binary Tree Implementation

[purestprodigy]

Hello, I am new here so please forgive me if I'm doing something wrong.

I was given an assignment where the requirement was to fill out a binary tree class using an array based implementation.

The header file was not to be touched, and we were to use a driver to test the program so most of the work was in the

Here's the .h file (CompleteBinaryTree.h):

#ifndef COMPLETE_BINARY_TREE
#define COMPLETE_BINARY_TREE

#include <vector>

/**
 * A binary tree that maintains the complete property
 */
template<class ItemType>
class CompleteBinaryTree {
private:
    static const int DEFAULT_CAPACITY = 6;
    int capacity;
    int itemCount;
    ItemType* items; // array of items

public:
    /* Constructors, destructor, and assignment operator */
    CompleteBinaryTree();
    ~CompleteBinaryTree();
    CompleteBinaryTree(const CompleteBinaryTree& other);
    CompleteBinaryTree& operator=(const CompleteBinaryTree& other);

    /**
     * Tests whether this binary tree is empty
     * @return true if the binary tree is empty otherwise false.
     */
    bool isEmpty();

    /**
     * Gets the height of the binary tree
     * @return the height of the binary tree.
     */
    int getHeight();

    /**
     * Gets the number of nodes in the binary tree
     * @return the number of nodes in the binary tree.
     */
    int getNumberOfNodes();

    /**
     * Gets the capacity of the backing array (the amount of total space).
     * @return the capacity of the backing array.
     */
    int getCapacity();

    /**
     * Adds a new node containing the given data to this binary tree. The node
     * is added to maintain the complete property of the binary tree. That is,
     * the binary tree is filled in left to right, top to bottom. If adding the
     * new node exceeds the capacity of the backing array, then the capacity of
     * the backing array is doubled.
     * @param newData the data for the new node.
     * @post the binary tree contains a new node and the complete property is
     * not violated.
     * @return true if the addition was successful, otherwise false.
 */
    bool add(const ItemType& newData);

    /**
     * Removes the node containing the given data item from this binary tree.
     * To maintain the complete property, the rightmost node at the lowest
     * level is placed at the location of the removed node. If the removal of
     * the node reduces the number of nodes to less than the current capacity
     * divided by four and greater than the default capacity, then the capacity
     * of the backing array is halved.
     * @param data the data value to remove form the binary tree.
     * @return true if the removal was successful, otherwise false.
     */
    bool remove(const ItemType& data);

    /**
     * Removes all the nodes from this binary tree. If the capacity of the
     * backing array is greater than the default capacity, then the capacity of
     * the backing array is changed to the default capacity.
     */
    void clear();

    /**
     * Tests whether a given entry occurs in this binary tree.
     * @param anEntry the entry to find.
     * @return true if the entry occurs in the tree, otherwise false.
     */
    bool contains(const ItemType& anEntry);

    /**
     * Traverse the tree in preorder and return a vector with the elements in
     * the order of the traversal.
     * @return a vector of the elements in a preorder traversal.
     */
    std::vector<ItemType> preorderTraverse();

    /**
     * Traverse the tree in inorder and return a vector with the elements in
     * the order of the traversal.
     * @return a vector of the elements in a inorder traversal.
 */
    std::vector<ItemType> inorderTraverse();

    /**
     * Traverse the tree in postorder and return a vector with the elements in
     * the order of the traversal.
     * @return a vector of the elements in a postorder traversal.
     */
    std::vector<ItemType> postorderTraverse();
};

#include "CompleteBinaryTree.cpp"
#endif 

Here is what I've done so far on the .cpp file (constructor was empty before, this if anything I want to make sure is correct -- psuedocode in place for isEmpty and getHeight)

(CompleteBinaryTree.cpp)

#include "CompleteBinaryTree.h"

template<class ItemType>
CompleteBinaryTree<ItemType>::CompleteBinaryTree(): capacity (DEFAULT_CAPACITY), itemCount (0) {

}

template<class ItemType>
CompleteBinaryTree<ItemType>::~CompleteBinaryTree() {

}

template<class ItemType>
CompleteBinaryTree<ItemType>::CompleteBinaryTree(const CompleteBinaryTree& other) {

}

template<class ItemType>
CompleteBinaryTree<ItemType>& CompleteBinaryTree<ItemType>::operator=(const CompleteBinaryTree& other) {
    return *this; // this is not a correct return value
}

template<class ItemType>
bool CompleteBinaryTree<ItemType>::isEmpty() {
    if (tree[index] == 0)
    return true; 
    else
    return false;
}

template<class ItemType>
int CompleteBinaryTree<ItemType>::getHeight() {
    if tree.isEmpty() == true
        return 0;
    else {
        int left_height = left.getHeight();
        int right_height = right.getHeight();
        int max = left_height + right_height + 1;
        return max;
    }

}

template<class ItemType>
int CompleteBinaryTree<ItemType>::getNumberOfNodes() {
    return itemCount; 
}

template<class ItemType>
int CompleteBinaryTree<ItemType>::getCapacity() {
    return capacity; 
    }

template<class ItemType>
bool CompleteBinaryTree<ItemType>::add(const ItemType & newData) {
        return false; // this is not a correct return value
    }

    template<class ItemType>
    bool CompleteBinaryTree<ItemType>::remove(const ItemType & data) {
        return false; // this is not a correct return value
    }

    template<class ItemType>
    void CompleteBinaryTree<ItemType>::clear() {

    }

    template<class ItemType>
    bool CompleteBinaryTree<ItemType>::contains(const ItemType & anEntry) {
        return false; // this is not a correct return value
    }

    template<class ItemType>
    std::vector<ItemType> CompleteBinaryTree<ItemType>::preorderTraverse() {
        std::vector<ItemType> result;
        return result; // this is not a correct return value
    }

    template<class ItemType>
    std::vector<ItemType> CompleteBinaryTree<ItemType>::inorderTraverse() {
        std::vector<ItemType> result;
        return result; // this is not a correct return value
    }

    template<class ItemType>
    std::vector<ItemType> CompleteBinaryTree<ItemType>::postorderTraverse() {
        std::vector<ItemType> result;
        return result; // this is not a correct return value
    }

And here's what my test driver looks like. The huge comment blocks are what my professor wants to be tested

(test_driver.cpp)

#include <iostream>
#include "CompleteBinaryTree.h"
using namespace std;

int main() {
    cout << "Initialize Complete Binary tree \n";
    CompleteBinaryTree<int> cbt;
    cout << "Get height of empty tree: \n";
    cbt.getHeight();
    cout << "\n";
    cout << "Add 0 to 16 to tree \n";
    for (int i = 0; i < 16; i++) {
        cbt.add(i);
    }
    cout << "Get height of filled tree: \n";
    cbt.getHeight();
    cout << "\n";
    cout << "Removing 0 from tree \n";
    cbt.remove(0);
    cout << "Pre-order Traverse: \n";
    cbt.preorderTraverse();
    cout << "\n";
    cout << "In-order Traverse: \n";
    cbt.inorderTraverse();
    cout << "\n";
    cout << "Post-order Traverse: \n";
    cbt.postorderTraverse();

    /* do the following
       1. display the height
       2. add 17 numbers (from 0 to 16) to the tree
       3. display the height again
       4. remove the number 0
       5. display the pre-order, in-order, post-order traveral of the tree

     sample output:
     -bash-4.1$ make test
     ./build/test_driver
     Height: 0
     Height: 5
     capacity: 24
     16, 1, 3, 7, 15, 8, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14,
     15, 7, 3, 8, 1, 9, 4, 10, 16, 11, 5, 12, 2, 13, 6, 14,
     15, 7, 8, 3, 9, 10, 4, 1, 11, 12, 5, 13, 14, 6, 2, 16,

     */


    return 0;
}

Thank you for your time.

[seeplus]

and the c++ question is......

[purestprodigy]

@seeplus
How do I fill in the rest of the CompleteBinaryTree.cpp to make it functional

[jonnin]

the easy way to do this is to just exchange array location index where you used to have a pointer, then everything is almost exactly like a regular pointer tree. Its wise to have the locations marked deleted when you remove something so you can recycle the cells, and you can use vector push-back to get more memory as you grow the thing if there are no empty cells and you want to use a vector or similar. Otherwise just mark all cells deletes on construction for a standard array and if they add when its full, print an error.

Do you have a specific question? Fill in the rest of it... is YOUR assignment. Pick one of the functions, and have a go at it, then test it and get it working, then move to the next one...

start with 'add'. by the way, adding 1-16 with the standard less left greater right will make a linked list degenerate tree. If you expect data to come into it sorted (either direction) you will also want a rebalance method, and if height > 1.25*lg(n) of the size and the size > something useful (say 10k? 100k?) call that to reorg it.

you can do any number of cheats on array-trees to exploit the array side of it, eg you may find that searching it is easier, or that rebalance is easier (sort it, take the median value as the root, and insert(not really, its really 'correct the pointers') from there going up and down from the median will be well balanced)