搜索二叉樹功能不起作用C++

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

但結果總是返回false不管樹包含鍵值與否。 你們能幫我檢查一下代碼嗎？我嘗試過調試，但仍然不知道。

謝謝！

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