0

这是我的代码：

  template <typename DataType> bool SearchValue(TreeNode<DataType> *root, DataType search_value)
{
    if(search_value != root->data)
    {
        if(root->right != NULL)
        {
            return SearchValue(root->right, search_value);
        }
        if (root->left != NULL)
        {
            return SearchValue(root->left, search_value);
        }
        return false;
    }
    else
    {
        return true;
    }
}

我无法使SearchValue功能正常工作。条件是不改变SearchValue函数的签名。问题如下：例如，我们尝试查找数据字段等于“90”的元素并且它存在于树中。有时这段代码会找到这个元素，有时却找不到——这取决于它在树中的位置。问题是如何让它每次都能正常工作。

我以这种方式构建树：

template <typename DataType> TreeNode<DataType> *BuildTree()
{
    TreeNode<DataType> *root = new TreeNode<DataType>(10, new TreeNode<DataType>(20), new TreeNode<DataType>(30));

    TreeNode<DataType> *curRoot = root;
    curRoot = curRoot->left;
    curRoot->left = new TreeNode<DataType>(40);
    curRoot->left->left = new TreeNode<DataType>(70);
    curRoot->right = new TreeNode<DataType>(50);
    curRoot = curRoot->right;
    curRoot->left = new TreeNode<DataType>(80, new TreeNode<DataType>(100), new TreeNode<DataType>(110));
    curRoot = root->right;
    curRoot->left = new TreeNode<DataType>(60);
    curRoot = curRoot->left;
    curRoot->right = new TreeNode<DataType>(90, new TreeNode<DataType>(120), new TreeNode<DataType>(130));

    return root;
}

我以这种方式测试搜索：

TreeNode<int> *treeRoot = BuildTree<int>();
    int valueToFind = treeRoot->data;
    cout << "Enter the value you'd like to find in the tree: ";
    cin >> valueToFind;
    cin.get();
    if(SearchValue(treeRoot, valueToFind) == true)
    {
        cout << "Value " << valueToFind << " was found!";
    }

我实现树的方式：

template <typename DataType> struct TreeNode
{
    TreeNode(DataType val, TreeNode<DataType> *leftPtr = NULL, TreeNode<DataType> *rightPtr = NULL)
    {
        left = leftPtr;
        right = rightPtr;
        data = val;
    }
    TreeNode<DataType> *left, *right;
    DataType data;
};
4

4 回答 4

5

如果存在，当前搜索将始终跟随右分支（然后永远不会跟随左分支）。如果数据在树中是有序的（这是典型的），代码应该检查根节点以决定是向左还是向右遍历。

于 2012-06-03T13:32:40.940 回答
1

改变

if(root->right != NULL)
{
    return SearchValue(root->right, search_value);
}
if (root->left != NULL)
{
    return SearchValue(root->left, search_value);
}
return false;

到

if(root->right != NULL)
{
    if (SearchValue(root->right, search_value))
        return true;
}
if (root->left != NULL)
{
    if (SearchValue(root->left, search_value))
        return true;
}
return false;

你现在拥有它的方式，它总是会沿着右分支走，如果在那里找到它就返回，从不检查左分支。

于 2012-06-03T14:09:10.427 回答
0

您可以清楚地看出代码是错误的，因为您从不进行比较。因此，默认情况下，代码不可能是正确的。

您需要比较以决定要关闭哪个分支，而不是简单地测试是否存在。

于 2012-06-03T14:07:16.217 回答
0

正如彼得亚历山大所说，你不能在右分支上返回，唯一的返回条件是相等并返回真，否则条件，需要继续左分支。

于 2012-06-03T14:21:24.820 回答