1

そして、バイナリ検索ツリーを実装しようとしていました:

template <typename T>
bool Tree<T>::search(TreeNode<T> *ptr, const T &key) {
if (ptr == 0) {
 cout<<"No such data: "<<key<<" in the tree"<<endl; 
 return false;
 }
else{
if (ptr->data == key) {
    cout<<"Find a node whose data is "<<key<<endl;
      return true;
} 
else if (ptr->data < key)  return search(ptr->leftPtr,key);

else  return search(ptr->rightPtr,key);
}
}

ただし、ツリーにキー値が含まれているかどうかに関係なく、結果は常に false を返します。コードをチェックするのを手伝ってもらえますか? デバッグを試みましたが、まだわかりません。

ありがとうございました！

4

1 に答える 1

2

左ツリーの降順のトラバーサル コンパレータは後方です。そのため、誤って正しいツリーに降りるとすぐに、その値を見つける可能性はなくなります。ルートのみ、ルートのみが正しく検出されます。

これ：

if (ptr->data < key)
    return search(ptr->leftPtr,key);
else
    return search(ptr->rightPtr,key);

次のように読む必要があります。

if (key < ptr->data) // <== note key is LESS THAN node.
    return search(ptr->leftPtr,key);
else
    return search(ptr->rightPtr,key);

そうは言っても、これを考慮してください：

template <typename T>
bool Tree<T>::search(TreeNode<T> *ptr, const T &key)
{
    if (ptr == 0) {
        cout<<"No such data: "<<key<<" in the tree"<<endl;
        return false;
    }

    if (key < ptr->data)
        return search(ptr->leftPtr, key);
    else if (ptr->data < key)
        return search(ptr->rightPtr, key);

    cout<<"Found a node whose data is "<< key << endl;
    return true;
}
于 2013-03-18T09:28:42.367 に答える