title: c++ data structures implement binary tree with a vector
body: <p>this is how I implement it: </p>
  
  <pre><code>#include "binary_tree_with_vector.h"
  #include &lt;vector&gt;
  using namespace std;
  
  
  
  template &lt;typename T&gt;
  class BinaryTree {
  
  public:
      class Position {
      private:
          int key;
      public:
          Position(int k) : key(k) {}
          friend class BinaryTree;
      };
  
  
  protected:
  
      vector&lt;T&gt; *array;
  
  public:
      BinaryTree() {
          array = new vector&lt;T&gt;;
          array-&gt;push_back(T());
      }
  
      int size() {
          return int(array-&gt;size()) - 1;
      }
  
      ~BinaryTree() {
          delete [] array;
      }
  
      BinaryTree&lt;T&gt;&amp; operator=(const BinaryTree&lt;T&gt;&amp; t) {
          if (this != &amp;t) {
              copyFrom(t);
          }
          return *this;
      }
  
      BinaryTree(const BinaryTree&lt;T&gt;&amp; t) {
          array = new vector&lt;T&gt;;
          copyFrom(t);
      }
  
      void print() {
          cout &lt;&lt; "size is: " &lt;&lt; size() &lt;&lt; endl;
          for (int i = 1; i &lt;= size(); i++) {
              cout &lt;&lt; array-&gt;at(i) &lt;&lt; "\t";
          }
          cout &lt;&lt; endl;
      }
  
  protected:
      void copyFrom(const BinaryTree&amp; t) {
          for (int i = 1; i &lt;= t.size(); i++) {
              array-&gt;push_back(t[i]);
          }
      }
  
  
  public:
  
      void swapElements(const Position&amp; p1, const Position&amp; p2) {
          T element = array[p1.key];
          array[p2.key] = array[p1.key];
          array[p1.key] = element;
      }
  
      void replaceElement(const Position&amp; p, const T&amp; e) {
          array[p.key] = e;
      }
  
      Position root() {
          return Position(array[1]);
      }
  
      bool isRoot(const Position&amp; p) {
          return p.key ==1;
      }
  
      bool isLeft(const Position&amp; p) {
          return p.key % 2 == 0;
      }
  
  
  
      Position parent(const Position&amp; p) {
          return Position(array-&gt;at(p.key / 2));
  
      }
  
      Position leftChild(const Position&amp; p) {
          return Position(array-&gt;at(p.key * 2));
      }
      Position rightChild(const Position&amp; p) {
          return Position(array-&gt;at(p.key * 2 + 1));
      }
  
      Position sibling(const Position&amp; p) {
          if (isLeft(p)) {
              return Position(array-&gt;at(p.key + 1));
          }
          return Position(array-&gt;at(p.key - 1));
      }
  
      bool isExternal(const Position&amp; p) {
          return p.key * 2 &gt; size();
      }
      bool isInternal(const Position&amp; p) {
          return !isExternal(p);
      }
  
      Position insert(const T&amp; e) {
          array-&gt;push_back(e);
          return
          (size());
      }
  
  
      T elementOf(const Position&amp; p) {
          return array-&gt;at(p.key);
      }
  
  };
  
  
  
  void binary_tree_with_vector() {
  
  
      typedef BinaryTree&lt;int&gt;::Position Position;
  
      BinaryTree&lt;int&gt; 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 &lt;&lt; "left child of root is: " &lt;&lt; tree.elementOf(leftChild) &lt;&lt; endl;
  
      Position rightChild = tree.rightChild(leftChild);
      cout &lt;&lt; "right child of left child of root is: " &lt;&lt; tree.elementOf(rightChild) &lt;&lt; endl;
  
      Position rightLeft = tree.leftChild(tree.rightChild(root));
      cout &lt;&lt; "right left is: " &lt;&lt; tree.elementOf(rightLeft) &lt;&lt; endl;
  
  
  
  }
  </code></pre>
  
  <p>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. </p>
  
  <p>When I run it, i got the error in the destructor </p>
  
  <pre><code>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) 
  </code></pre>