C ++ 이진 검색 트리 재귀 검색 기능

StackOverflow https://stackoverflow.com/questions/245628

  •  05-07-2019
  •  | 
  •  

문제 

template <class T>
bool BST<T>::search(const T& x, int& len) const
{
    return search(BT<T>::root, x);
}


template <class T>
bool BST<T>::search(struct Node<T>*& root, const T& x)
{
   if (root == NULL)
       return false;
   else
      {
         if (root->data == x)
             return true;
         else if(root->data < x)
             search(root->left, x);
         else 
             search(root->right, x);                 
      }             
}

그래서 이것은 T 노드가있는 내 BST 클래스의 검색 기능입니다. X는 트리 내에서 검색되는 데이터이며, Len은 존재하는 경우 일치하는 노드를 만들기 위해 이동 해야하는 노드의 양입니다. 나는 아직도 내 과제를 점진적으로 개발하고 있다는 것을 외워지지 않았습니다. 나는 이것을함으로써 그것을 부르고있다 :

if(t.search(v[1], len) == true)
       cout << endl << "true";

v는 그것을 비교하기 위해 만들어야 할 벡터 일 뿐이므로 int와 함께 제공하는 것입니다. 내가받는 오류 :

BST.h: In member function âbool BST<T>::search(const T&, int&) const [with T = int]â:
prog5.cc:24:   instantiated from here    
BST.h:78: error: no matching function for call to âBST<int>::search(Node<int>* const&, const int&) constâ    
BST.h:76: note: candidates are: bool BST<T>::search(const T&, int&) const [with T = int]
BST.h:83: note:                 bool BST<T>::search(Node<T>*&, const T&) [with T = int]

그래서 내가 뭘 잘못하고 있는지 또는 내가 어디에서 잘못하고 있는지 잘 모르겠습니다.

도움이 되었습니까?

해결책

괜찮아, bool BST<T>::search(struct Node<T>*& root, const T& x) 아마도 그렇게 될 것입니다. bool BST<T>::search(struct Node<T>*& root, const T& x) const. 기본적으로, 당신은 const 함수에서 비 초보 함수를 호출했으며 이것은 no-no입니다.

BTW, 이것은 나에게 의심되는 것 같습니다. "struct Node<T>*&"... 아마도 &와 함께 일할 것입니다. Node<T>*...하지만 아마도 당신은 그것을 필요로합니다 구조?

또한 이것은 C ++이며, 노드를 구조물로 남겨 둘 이유가 없습니다 ... 구조 매개 변수 정의에서 단지 나쁘게 보입니다. IMHO. 노드를 클래스로 만드는 이유는 무엇입니까?

다른 팁

검색 코드에는 여러 가지 문제가 있습니다.

  • 정렬 순서는 뒤로, 노드 데이터가 검색하는 것보다 적은 경우 왼쪽 분기가 아닌 오른쪽 분기에서 검색해야합니다.

  • 재귀 호출 결과를 반환해야합니다

  • 왜 당신이 통과하는지는 확실하지 않습니다 root 참조로. 대신 통과해야합니다 const 자격을 갖춘 포인터와 방법 본문이 있어야합니다 const 자격이 있습니다.

대안은 다음과 같습니다.

template <class T>
bool BST<T>::search(const struct Node<T> *root, const T& x) const {
    if (root == NULL)
        return false;
    else
    if (root->data == x)
        return true;
    else
    if (root->data < x)
        return search(root->right, x);
    else 
        return search(root->left, x);
}

그리고 여기에 간단한 비 재귀 구현이 있습니다.

template <class T>
bool BST<T>::search(const struct Node<T> *root, const T& x) const {
    while (root != NULL) {
        if (root->data == x)
            return true;
        if (root->data < x)
            root = root->right;
        else 
            root = root->left;
    }
    return false;
}

알고리즘 :

  1. 노드 값 데이터를 가져옵니다.
  2. 값을 찾거나 나무를 넘어 갈 때까지 3 단계를 5 단계로 반복하십시오.
  3. 데이터가 루트 노드 값과 같으면 검색이 성공하고 알고리즘을 종료합니다.
  4. 데이터가 루트 노드 값보다 작 으면 왼쪽 하위 트리를 검색해야합니다.
  5. 그렇지 않으면 데이터는 루트 노드 값보다 적으므로 왼쪽 하위 트리를 검색해야합니다.
  6. 출력 인쇄 메시지 "발견"또는 "찾을 수 없음".

C ++ 구현

    node* search(node* root, int data)
    {
     if (root==NULL || root->data==data) return root;

     if (root->data < data)   return search(root->right, data);

     return search(root->left, data);
   }
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top