c++ data structures implement binary tree with a vector
Solution 1
You are allocating a single vector
here
array = new vector<T>;
but are attempting to delete
an array of vector
s here
delete [] array;
Change the last line to
delete array;
Solution 2
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();
}
Comments
-
OMGPOP almost 2 years
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)