在 BST 中搜索值代码

Question

所以我需要在main中调用contain()函数。然后递归调用containsValue()函数，看传入的值是否在BST中。当我搜索根值时，我得到的 return 值为 true，但是，我搜索的任何其他值都为 false。任何帮助都会很棒。谢谢

BST.H

#include "stdafx.h"
#include <iostream>
#include <cstddef>
#include <string>
using namespace std;


#ifndef BST_H_
#define BST_H_

template <class bstdata>
class BST
{
private:
    struct Node
    {
        bstdata data;
        Node* left;
        Node* right;

        Node() : left(NULL), right(NULL){}
        Node(bstdata newdata) : left(NULL), right(NULL), data(newdata){}
    };

    typedef struct Node* Nodeptr;

    Nodeptr root;
    int size;

    /** Private Helper Functions **/

    void addValue(Nodeptr root, bstdata value);
    void printInOrder(Nodeptr root);
    void deleteTree(Nodeptr root);
    bool containsValue(Nodeptr root, bstdata);

public:
    BST();
    ~BST();
    bool isEmpty();
    int getSize();
    void add(bstdata value);
    bstdata getRoot();
    void inOrderPrint();
    void preOrderPrint();
    void postOrderPrint();
    bool contains(bstdata value);

};


/**Private helper functions*/

template <class bstdata>
void BST<bstdata>::addValue(Nodeptr root, bstdata value)
{
    if (value == root->data)
        return;

    if (value < root->data)
    {
        if (root->left == NULL)
        {
            root->left = new Node(value);
            size++;
        }
        else //(root->left != NULL);
            addValue(root->left, value);
    }

    if(value > root->data)
    {
        if (root->right == NULL)
        {
            root->right = new Node(value);
            size++;
        }
        else
            addValue(root->right, value);
    }
}

template <class bstdata>
void BST<bstdata>::printInOrder(Nodeptr root)
{
    if (root != NULL)
    {
        printInOrder(root->left);
        cout << root->data << " ";
        printInOrder(root->right);
    }
}

template <class bstdata>
void BST<bstdata>::deleteTree(Nodeptr root)
{
    if (root != NULL)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }

}

template<class bstdata>
bool BST<bstdata>::containsValue(Nodeptr root, bstdata value)
{
    if (value == root->data)
        return true;

    if (value < root->data)
    {
        if (root->left == NULL)
            return false;
        else // (root->left !=NULL)
            containsValue(root->left, value);
    }

    if (value > root->data)
    {
        if (root->right == NULL)
            return false;
        else //root->right !=NULL
            containsValue(root->right, value);
    }

    return  false;
}


/**Public functions*/

template <class bstdata>
BST<bstdata>::BST() : size(0), root(NULL){};

template <class bstdata>
void BST<bstdata>::add(bstdata value)
{
    if (root == NULL)
    {
        root = new Node(value);
        size++;
    }
    else
        addValue(root, value);
}


template <class bstdata>
bstdata BST<bstdata>::getRoot()
{
    if (size == 0)
        cout << "getRoot: there is no root in the BST" << endl;
    else
        return root->data;

}

template <class bstdata>
int BST<bstdata>::getSize()
{
    if (size == 0)
        cout << "getSize(): There is nothing in the tree, size = 0" << endl;
    else
        return size;
}

template <class bstdata>
bool BST<bstdata>::isEmpty()
{
    if (size == 0)
        return true;
    else
        return false;
}


template <class bstdata>
void BST<bstdata>::inOrderPrint()
{

    if (size == 0)
        cout << isEmpty() << endl;
    if (root != NULL)
    {
        printInOrder(root->left);
        cout << getRoot() << " ";
        printInOrder(root->right);
    }

}

template <class bstdata>
void BST<bstdata>::preOrderPrint()
{
    if (size == 0)
        cout << isEmpty() << endl;
    if (root != NULL)
    {
        cout << getRoot() << " ";
        printInOrder(root->left);
        printInOrder(root -> right);
    }
}

template <class bstdata>
void BST<bstdata>::postOrderPrint()
{
    if (size == 0)
        cout << isEmpty() << endl;
    if (root != NULL)
    {
        printInOrder(root->left);
        printInOrder(root->right);
        cout << getRoot() << " ";
    }
}

template <class bstdata>
BST<bstdata>::~BST()
{
    deleteTree(root);
}

template<class bstdata>
bool BST<bstdata>::contains(bstdata value)
{
    if (value == root->data)
        return true;
    else
        return containsValue(root, value);
}

#endif

BSTTEST.cpp

#include "stdafx.h"
#include "BST.h"
#include <iostream>
#include <cstddef>
#include <string>
using namespace std;


int main()
{

    BST<int> B;

    B.getSize();
    cout << B.isEmpty() << endl;

    B.add(7);
    B.add(1);
    B.add(5);
    B.add(15);
    B.add(10);
    B.add(11);

    cout << B.isEmpty() << endl;
    cout << "Root of tree: " << B.getRoot() << endl;
    cout << B.getSize() << endl;

    B.inOrderPrint();
    cout << endl << endl;
    B.preOrderPrint();
    cout << endl << endl;
    B.postOrderPrint();
    cout << endl << endl;
    cout << B.contains(1) << endl;
    cout << B.contains(7) << endl;
    cout << B.contains(78) << endl;
    cout << B.contains(11) << endl;



    return 0;
}

Answer 1

您忘记了 return 您的结果。当您的 containsValue() 函数迭代地调用自身时，它要么找到 return 为真的值，要么到达 BST 的底部 return 为假的值。一旦找到目标值，它 return 就是调用它的函数的真实结果，它本身只有一次。结果既不存储也不 returned。因此它无法 return 最终结果一直返回到它的第一次调用。迭代调用函数时需要加上'return'。我已经添加了您遗漏的两个 'return'。

template<class bstdata>
bool BST<bstdata>::containsValue(Nodeptr root, bstdata value)
{
    if (value == root->data)
        return true;

    if (value < root->data)
    {
        if (root->left == NULL)
            return false;
        else // (root->left !=NULL)
            return containsValue(root->left, value);
    }

    if (value > root->data)
    {
        if (root->right == NULL)
            return false;
        else //root->right !=NULL
            return containsValue(root->right, value);
    }

    return  false;
}

Answer 2

将您的代码分成 if-else if-else 块，如下所示：

template<class bstdata>
bool BST<bstdata>::containsValue(Nodeptr root, bstdata value)
{
    if (value == root->data)
        return true;

    else if (value < root->data)
    {
        if (root->left == NULL)
            return false;
        else // (root->left !=NULL)
            containsValue(root->left, value);
    }

    else if (value > root->data)
    {
        if (root->right == NULL)
            return false;
        else //root->right !=NULL
            containsValue(root->right, value);
    }

    else return false;
}

Answer 3

您的 contains 似乎太复杂了。我会尝试这样的事情

template<class bstdata>
bool BST<bstdata>::containsValue(Nodeptr node, bstdata value)
{
    if (node == nullptr)
        return false;
    if (value == node->data)
        return true;

    if (value < node->data)
        return containsValue(node->left, value);
    else
        return containsValue(node->right, value);
}

template<class bstdata>
bool BST<bstdata>::contains(bstdata value)
{
    return containsValue(root, value);
}

更有效一点的迭代版本：

template<class bstdata>
bool BST<bstdata>::containsValue(Nodeptr node, bstdata value)
{
    while (node)
    {
        if (value == node->data)
            return true;

        node = value < node->data ? node->left : node->right;
    }
    return false;
}

在 BST 中搜索值代码

Searching BST for value code

c++

binary-search-tree