BST中的向量搜索

Question

我的节点结构：

struct BstNode{
    string nameValue; // Names
    vector<int> pseudoIDS; // Unique IDs
    BstNode* left;
    BstNode* right;
};

我想在向量中搜索ID。我错了，bool，现在回来了--我想搜索是错的。

bool Search(BstNode* root, int data, vector<int>& ids){
int i = 0; // vector position
do{
   if(root == NULL){
     return false;
}
else if (root->pseudoIDS[i] == data){
    return true;
}
else if (data <= root->pseudoIDS[i]) {
     return Search(root->left, data);
}
else
     return Search(root->right, data);
   i++;
   }while(i == ids.size())

}

_____ ALL CODE____

现在，当我查找ID时，如果按ID搜索的结果为正，则返回第一个节点，即使为搜索选择的ID应该给出第三个节点(例如)

 struct BstNode{
 string nameValue; // Names
 vector<int> pseudoIDS; // Unique IDs
 BstNode* left;
 BstNode* right;
 };

 BstNode* GetNewNode(string name, vector<int>& ids){
 BstNode* newNode = new BstNode();
 newNode->nameValue = name;
 newNode->pseudoIDS.insert(newNode->pseudoIDS.end(), ids.begin(), ids.end()); // Inserting ids i     nto Node
 newNode->left = newNode->right = NULL;
 return newNode;
 }

 BstNode* Insert(BstNode* root, string name, vector<int>& ids){
 // Tree is empty
 if (root == NULL) {
 root = GetNewNode(name, ids);
 return root;
 }
 else if(name <= root->nameValue){
 root->left = Insert(root->left, name, ids);
 }     
 else{
 root->right = Insert(root->right, name, ids);
 }
 return root;
 }

 void PrintTree (BstNode* node){
 if (node == NULL){ return; }
 PrintTree(node->left);

 cout << "Node string: " << node->nameValue << endl;
 PrintTree(node->right);
 }

 bool search(BstNode* root, int data)
 {
 if(root == NULL || root->pseudoIDS.size() == 0) return false;
 // we need a max and min counter to see where the element may lie if its not in this root node
 int max = root->pseudoIDS[0];
 int min = root->pseudoIDS[0];

 for(unsigned int i = 0; i < root->pseudoIDS.size(); i++) {
 if(root->pseudoIDS[i] == data) return true;
 // update max and min
 if(root->pseudoIDS[i] > max) max = root->pseudoIDS[i];
 if(root->pseudoIDS[i] < min) min = root->pseudoIDS[i];
 }

 if(data > max) return search(root->right, data); // if the element we are looking for is greater than max,      we search the right node
 else if(data < min) return search(root->left, data); // if the element is less than the min, we search the left
 else return false; // the element had to be in this vector if it existed
 }

 int main(){
 BstNode* root = NULL; // Creating empty BST


 // TEST
 vector<int> test;
 vector<int> test2;
 vector<int> test3;

 for (int i = 0; i < 3; i++){ test.push_back(i); }
 for (int i = 10; i < 12; i++){ test2.push_back(i); }
 for (int i = 56; i < 60; i++){ test3.push_back(i); }

 root = Insert(root, "Abuels", test);
 root = Insert(root, "Caves", test2);
 root = Insert(root, "Zapes", test3);
 root = Insert (root, "Bib", test);

 // Print
 PrintTree(root);

 cout << "Searching by ID: " << endl;

 if(search(root, 11) == 1){
 cout << root->nameValue;
 }
 else
 cout << "nope";


 return 0;
 }

Answer 1

基于我的评论这里有一个解决方案。我假设您的it向量没有排序(如果对其进行排序，则可以对其进行更多的优化)。这与您的解决方案不同，因为它首先检查根节点的向量，然后决定元素是否位于右节点、左节点，还是两者都不在。我还假设您的BST设置如下:左侧节点的值低于根节点，右侧节点的值高于根节点。如果你这样做的话，你只需要做一些小的改变。

bool search(BstNode* root, int data)
{
    if(root == NULL || root->values.size() == 0) return false;
    // we need a max and min counter to see where the element may lie if its not in this root node
    int max = root->values[0];
    int min = root->values[0];

    for(unsigned int i = 0; i < root->values.size(); i++) {
        if(root->values[i] == data) return true;
        // update max and min
        if(root->values[i] > max) max = root->values[i];
        if(root->values[i] < min) min = root->values[i];
    }

    if(data > max) return search(root->right, data); // if the element we are looking for is greater than max, we search the right node
    else if(data < min) return search(root->left, data); // if the element is less than the min, we search the left
    else return false; // the element had to be in this vector if it existed
}

int main()
{
    // initalizing the structures:
    BstNode left = {"Left", std::vector<int>(), NULL, NULL};
    BstNode right = {"Right", std::vector<int>(), NULL, NULL};
    BstNode root = {"Root", std::vector<int>(), &left, &right};

    // left has values lower than root
    // right has values higher than root
    // slightly randomized to show it still works
    left.values.push_back(0);
    left.values.push_back(2);
    left.values.push_back(1);
    root.values.push_back(4);
    root.values.push_back(2);
    root.values.push_back(3);
    right.values.push_back(5);
    right.values.push_back(7);
    right.values.push_back(6);

    std::cout<< search(&root, 0) << std::endl; // left node test case; should return true
    std::cout<< search(&root, 8) << std::endl; // impossible case; should return false
    std::cout << search(&root, 7) << std::endl; // right node test case; should return true
    std::cout << search(&root, 3) << std::endl; // root node test case; should return true

    return 0;
}

编辑:回答第二个问题：

从您的主要测试方法来看，这是不正确的：

if(search(root, 11) == 1){
cout << root->nameValue; // this will _always_ print the root node's name
}
else
cout << "nope";

我猜您希望打印值所在的节点的名称。要解决这个问题，您可以创建另一个名为find的函数，它可以执行相同的任务，但它返回指向节点的指针。

例如：

BstNode* find(BstNode* root, int data)
{
    if(root == NULL || root->values.size() == 0) return NULL;
    // we need a max and min counter to see where the element may lie if its not in this root node
    int max = root->values[0];
    int min = root->values[0];

    for(unsigned int i = 0; i < root->values.size(); i++) {
        if(root->values[i] == data) return root;
        // update max and min
        if(root->values[i] > max) max = root->values[i];
        if(root->values[i] < min) min = root->values[i];
    }

    if(data > max) return find(root->right, data); // if the element we are looking for is greater than max, we search the right node
    else if(data < min) return find(root->left, data); // if the element is less than the min, we search the left
    else return NULL; // the element had to be in this vector if it existed
}

这将返回一个指向节点的指针，该节点包含您要查找的内容。所以你会在你的测试中这样做：

BstNode* ptr = find(root, 11);
if(ptr != NULL){
 cout << ptr->nameValue;
}
else
cout << "nope";