검색 이진 트리 기능은 ++

Question

c를 작동하지 난 이진 검색 트리를 구현하기 위해 노력했다 :

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

은 다음과 같이 읽어야

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