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

Peter Alexander が言ったように、右分岐で戻ることはできません。唯一の戻り条件は、equal で true を返すことです。else 条件の場合は、左分岐を続行する必要があります。

于 2012-06-03T14:21:24.820 に答える
0

比較を実行しないため、コードが間違っていることがはっきりとわかります。したがって、デフォルトでは、コードは正しくありません。

単純に存在をテストするのではなく、どのブランチをダウンさせるかを決定するために比較する必要があります。

于 2012-06-03T14:07:16.217 に答える