c++ data structures implement binary tree with a vector

Question

this is how I implement it:

#include "binary_tree_with_vector.h"
#include <vector>
using namespace std;



template <typename T>
class BinaryTree {

public:
    class Position {
    private:
        int key;
    public:
        Position(int k) : key(k) {}
        friend class BinaryTree;
    };


protected:

    vector<T> *array;

public:
    BinaryTree() {
        array = new vector<T>;
        array->push_back(T());
    }

    int size() {
        return int(array->size()) - 1;
    }

    ~BinaryTree() {
        delete [] array;
    }

    BinaryTree<T>& operator=(const BinaryTree<T>& t) {
        if (this != &t) {
            copyFrom(t);
        }
        return *this;
    }

    BinaryTree(const BinaryTree<T>& t) {
        array = new vector<T>;
        copyFrom(t);
    }

    void print() {
        cout << "size is: " << size() << endl;
        for (int i = 1; i <= size(); i++) {
            cout << array->at(i) << "\t";
        }
        cout << endl;
    }

protected:
    void copyFrom(const BinaryTree& t) {
        for (int i = 1; i <= t.size(); i++) {
            array->push_back(t[i]);
        }
    }


public:

    void swapElements(const Position& p1, const Position& p2) {
        T element = array[p1.key];
        array[p2.key] = array[p1.key];
        array[p1.key] = element;
    }

    void replaceElement(const Position& p, const T& e) {
        array[p.key] = e;
    }

    Position root() {
        return Position(array[1]);
    }

    bool isRoot(const Position& p) {
        return p.key ==1;
    }

    bool isLeft(const Position& p) {
        return p.key % 2 == 0;
    }



    Position parent(const Position& p) {
        return Position(array->at(p.key / 2));

    }

    Position leftChild(const Position& p) {
        return Position(array->at(p.key * 2));
    }
    Position rightChild(const Position& p) {
        return Position(array->at(p.key * 2 + 1));
    }

    Position sibling(const Position& p) {
        if (isLeft(p)) {
            return Position(array->at(p.key + 1));
        }
        return Position(array->at(p.key - 1));
    }

    bool isExternal(const Position& p) {
        return p.key * 2 > size();
    }
    bool isInternal(const Position& p) {
        return !isExternal(p);
    }

    Position insert(const T& e) {
        array->push_back(e);
        return
        (size());
    }


    T elementOf(const Position& p) {
        return array->at(p.key);
    }

};



void binary_tree_with_vector() {


    typedef BinaryTree<int>::Position Position;

    BinaryTree<int> tree;

    Position root = tree.insert(1);
    tree.insert(2);
    tree.insert(3);
    tree.insert(4);
    tree.insert(5);
    tree.insert(6);
    tree.insert(7);
    tree.print();

    //1
    //2     3
    //4 5   6 7

    Position leftChild = tree.leftChild(root);
    cout << "left child of root is: " << tree.elementOf(leftChild) << endl;

    Position rightChild = tree.rightChild(leftChild);
    cout << "right child of left child of root is: " << tree.elementOf(rightChild) << endl;

    Position rightLeft = tree.leftChild(tree.rightChild(root));
    cout << "right left is: " << tree.elementOf(rightLeft) << endl;



}

The position is just a encapsulation wrap around the rank (the key or index), since the implementation detail of the tree should be hidden outside.

When I run it, i got the error in the destructor

size is: 5
chap6(607,0x7fff7bea6310) malloc: *** error for object 0x100103a88: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
1   2   3   4   5   (lldb)

user657267 · Accepted Answer · 2014-04-25 07:49:43Z

3

You are allocating a single vector here

array = new vector<T>;

but are attempting to delete an array of vectors here

delete [] array;

Change the last line to

delete array;

edited Apr 25, 2014 at 7:49

answered Apr 25, 2014 at 7:43

user657267

21.1k5 gold badges65 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

OMGPOP Over a year ago

oh so deleting vector is diff from deleting array?

user657267 Over a year ago

@OMGPOP a vector is just another object, if you allocate a single object you use delete, if you allocate an array of objects you use delete[]. Here you have allocated a single object, the fact that it happens to be a vector does not mean it is an array.

user743414 Over a year ago

There's another mistake in his code. There are 6 Items in your array not 5!! In his constructor he's adding the first item.

OMGPOP Over a year ago

that's what i intended to do. since you can compute left/right child of node n as 2*n and 2*n + 1

user743414 Over a year ago

Ok maybe it's not a mistake, but you can do the same with a zero based index. Btw you should remove your pointer to vector<T> array.

Richard Hodges · Accepted Answer · 2014-04-25 08:05:40Z

3

Whenever there is a call to "new" or "delete" in a c++ program, it's a hint that there is a better (read safer) way available.

If you are hell-bent on using dynamic memory allocation, make the member variable "array" one of these:

std::unique_ptr< std::vector< T > > // use auto_ptr prior to c++11

Alternatively, this class can be slightly modified to make it more efficient, safer and easier to maintain by simply encapsulating a vector rather than a pointer to a vector. Note that the destructor and copy operators are now implicitly and correctly generated by the compiler:

#include <vector>
#include <iostream>

using namespace std;

template <typename T>
class BinaryTree {

public:
    class Position {
    private:
        int key;
    public:
        Position(int k) : key(k) {}
        friend class BinaryTree;
    };


protected:

    vector<T> _array;

public:
    BinaryTree()
    : _array(1) {
    }

    int size() const {
        return int(_array.size() - 1);
    }

    BinaryTree& operator=(const BinaryTree& t) = default;

    BinaryTree(const BinaryTree& t) = default;

    void print() {
        cout << "size is: " << size() << endl;
        for (int i = 1; i <= size(); i++) {
            cout << _array.at(i) << "\t";
        }
    }

public:

    void swapElements(const Position& p1, const Position& p2) {
        swap(_array[p1.key], _array[p2.key]);
    }

    void replaceElement(const Position& p, const T& e) {
        _array[p.key] = e;
    }

    Position root() const {
        return Position(_array[1]);
    }

    static bool isRoot(const Position& p) {
        return p.key ==1;
    }

    static bool isLeft(const Position& p) {
        return p.key % 2 == 0;
    }

    Position parent(const Position& p) const {
        return Position(_array[p.key / 2]);

    }

    Position leftChild(const Position& p) const {
        return Position(_array[p.key * 2]);
    }

    Position rightChild(const Position& p) const {
        return Position(_array[p.key * 2 + 1]);
    }

    Position sibling(const Position& p) const {
        if (isLeft(p)) {
            return Position(_array[p.key + 1]);
        }
        return Position(_array[p.key - 1]);
    }

    bool isExternal(const Position& p) const {
        return p.key * 2 <= size();
    }
    bool isInternal(const Position& p) const {
        return !isExternal(p);
    }

    Position insert(const T& e) {
        _array.push_back(e);
        return
        (size());
    }

};



int main() {

    BinaryTree<int> tree;
    tree.insert(1);
    tree.insert(2);
    tree.insert(3);
    tree.insert(4);
    tree.insert(5);
    tree.print();


}

answered Apr 25, 2014 at 8:05

Richard Hodges

70.3k8 gold badges103 silver badges157 bronze badges

6 Comments

OMGPOP Over a year ago

if i decided to use a real array instead (protected: T * array; and in constructor, array = new T[], do i have to use pointer?

Richard Hodges Over a year ago

operator 'new' returns a pointer so yes, but the safer way to store a pointer returned by 'new' is to initialise a unique_ptr with it. Then you don't have to remember to 'delete' it. The other advantage of unique_ptr is that the compiler will not compile attempts to trivially copy it, forcing you to write code to do the right thing. As mentioned though, better to use a vector rather than vector* - it's actually more efficient and safer. There is no reason not to.

Richard Hodges Over a year ago

Another thing you may want to address is the fact that your 'array' member is protected. This effectively makes it part of the classes public interface (when someone inherits from you). This is probably not what you intend. In general, you'll have a happier time if you make all data private and some methods public. Under close examination there is rarely a good case for protected methods and almost never a good case for protected data, unless that data is intended to be part of the interface - in which case make it public.

OMGPOP Over a year ago

the text book uses protected all the time (and I agree with it) cpp.datastructures.net

Richard Hodges Over a year ago

I guess that's your choice. I hope I don't have to maintain any code you write :-)

|

Collectives™ on Stack Overflow

c++ data structures implement binary tree with a vector

2 Answers 2

5 Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related