我需要仅使用向量制作二进制搜索树，并且能够在/ pre / post-order中打印;向量中的第一个数字是二叉树的头部 . 我创建了一个带有一个向量的类来存储值，另一个向量用于存储它们在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();
};
我正在使用递归并在节点没有子节点时插入值;如果值小于或等于节点的值，则为左子节点，否则为右子节点 . 我不确定如何在addNode（）中进行索引，以便它与正确的值进行比较，并且不会超过向量的大小 .
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] << " ";
}
}
然后，在主要：
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();
这似乎只在某些情况下起作用，但非常不一致 . 任何帮助表示赞赏 .