0

I need to make a Binary Search Tree using only vectors and be able to print in/pre/post-order; the first number in the vector is the head of Binary Tree. I made a class with one vector to store values and another vector to store their locations in BST:

class BST {
 private:
  std::vector<int> binaryVector;
  std::vector<int> posVector;
 public:
  BST() {};
  void addNode(int);
  void addRecursively(int, int j = 0, int i = 0);
  bool hasChild(int);
  void printPos();
};

I am using recursion and inserting a value if the node does not have a child; to the left child if the value is less than or equal to the node's value and otherwise to the right child. I am not sure how to index in the addNode(), so that it compares to the right values and does not go over the size of a vector.

bool BST::hasChild(int i) {
  auto t = std::find(posVector.begin(), posVector.end(), i);
  if(t != posVector.end())
    return true;
  else
    return false;
}
void BST::addNode(int itm) {
  if(!binaryVector.size()) {
    binaryVector.push_back(itm);
    posVector.push_back(0);
  }else{
    addRecursively(itm);
  }
}
void BST::addRecursively(int itm, int j, int i) {
  std::vector<int> V = binVector;
  int right = 2 * (i + 1);
  int left = 2 * i + 1;
  int len = V.size();
  auto id = std::find(V.begin(), V.end(), i);
  if(itm <= V[i]) {
    if(!hasChild(left)) {
      binaryVector.push_back(itm);
      posVector.push_back(left);
      return;
    }

    addRecursive(itm, ++j, left);
  }else if(itm > V[i]){
    if(!hasChild(right)) {
      binaryVector.push_back(itm);
      posVector.push_back(right);
      return;
    }

    addRecursive(itm, ++j, right);
  }
}
void BST::printPos() {
  for(int i = 0, size = binaryVector.size(); i < size; i++) {
    std::cout << posVector[i] << " ";
  }
}

Then, in the main:

BST vTree;
std::vector<int> a = {4,3,2,1}; // posVector: 0, 1, 3, 7
std::vector<int> b = {1,2,3,4}; // posVector: 0, 2, 6, 4
std::vector<int> c = {5,4,6,8,9,7} // posVector: 0, 1, 2, 6, 14, 29
for (int i=0; i<b.size(); i++) 
    vTree.addNode(b[i]);
vTree.printPos();

This seems to work only in certain situation but is very inconsistent. Any help is appreciated.

phoxd
  • 1,546
  • 3
  • 12
  • 26
  • This seems like a poor design choice to me. How do you handle a tree that isn't full and/or complete? How do you mark the indices in your vector that are empty? – MFisherKDX Nov 13 '17 at 02:11
  • I couldn't think of other way to make it so that I would be able to print in/pre/post-order. – phoxd Nov 13 '17 at 02:15
  • A complete tree or a heap can be represented by an array / vector in the way you describe. But inserting elements in the way you describe will not maintain this property. Maybe someone else sees something I'm missing. But one solution would be to abandon the vector approach and write a node class to have 3 elements: an integer, a right Node and a left Node. – MFisherKDX Nov 13 '17 at 02:21
  • But I cannot use linked lists only vectors. – phoxd Nov 13 '17 at 02:23
  • I think you are confused. I suggest you ask whoever gave you these requirements for clarification. If you must represent a binary tree as a vector, and continue to insert as described, see this post. Especially the second answer as it relates to using some indicator to represent `NULL` nodes in the vector. https://stackoverflow.com/questions/8256222/binary-tree-represented-using-array – MFisherKDX Nov 13 '17 at 02:31

0 Answers0