Функция поиска Бинарного дерева не работает с ++

Question

и я пытался реализовать бинарный поиск по дереву:

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); 
} 
} 

Но результат всегда возвращает ложь независимо от того, что дерево не содержит ключевое значение или нет. Могут ли ребята помочь мне проверить код? Я пробовал отлаживать, но все равно не знаю.

Спасибо!

Answer 1

Ваш обходной компаратор для опускания левого дерева назад. Таким образом, как только вы неправильно спуститесь в дерево , у вас нет шансов когда-либо найти это значение. Только корень и корень будут всегда найдены правильно.

Это:

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; 
}