문제

나는 특정 값에 대해 이진 트리를 검색하기 위해 반복적 인 기능을 작성하고 있습니다. 클래스를 제네릭하는 방법에 들어가기 전까지는 서명 된 INT에 현지화됩니다.

내 클래스가 BinarySearchtree라고 가정하고 트리의 루트 노드에 대한 포인터가 있다고 가정합니다. 또한 노드가 인서트 기능을 통해 삽입되고 두 어린이에게 포인터가 있다고 가정합니다. Node Struct의 약식 버전은 다음과 같습니다.

struct Node
{
   public:
      Node *left_, *right_;
      int value_

      Node(int val) : value_(val), left_(0), right_(0) { }
      //done in this manner to always make sure blank children are
      //init to zero, or null
      Node(int val, Node *left, Node *right) : value_(val), left_(0), right_(0) 
          { left_ = left; right_ = right; } 
}

따라서 노드의 innit 포인터가 무효라고 안전하게 가정 할 수 있습니다.

내 코드는 다음과 같습니다.

int BinarySearchTree::search(int val)
{
    Node* next = this->root();

    while (next->left() != 0 || next->right () != 0)
    {
        if (val == next->value())
        {
            return next->value();
        }    
        else if (val < next->value())
        {
            next = next->left();   
        }
        else if (val > next->value())
        {
            next = next->right();
        }
    } 

    //not found
    return 0;
}

이 코드는 두 가지 이유로 친구에 의해 거부됩니다.

1) 다음에 자녀가 없으면 둘 다 0으로 평가하고 루프를 조기에 빠져 나갈 것입니다 (검색 된 Val을 Next의 값에 대해 결코 확인하지 않겠습니다).

2) 다음에 한 자녀가 있지만 검색하는 데이터가 나무의 빈쪽에 있어야한다면 다음은 0으로 설정되며 다음 (0)을 왼쪽과 오른쪽으로 비교하여 다시 루프됩니다. 나무가 좋아요 while(0->left()), 정의되지 않은 행동을 초래합니다.

두 문제에 대한 해결책은 루프 조건에 있다고 들었지만 상황을 쉽게 해결하기 위해 무엇을 할 수 있는지 알 수 없습니다. 스택 오버플로 커뮤니티가 통찰력을 제공 할 수 있습니까?

도움이 되었습니까?

해결책

다음에 루프가 무효가되지 않으면 테스트해야한다고 생각합니다.

int BinarySearchTree::search(int val)
{
    Node* next = this->root();

    while (next)
    {
        if (val == next->value())
        {
            return next->value();
        }    
        else if (val < next->value())
        {
            next = next->left();   
        }
        else if (val > next->value())
        {
            next = next->right();
        }
    } 

    //not found
    return 0;
}

다른 팁

이 시도:

while (next != NULL) ?

우선, 왜 당신이 int를 반환하고 있는지 잘 모르겠습니다. 트리에서 0을 찾고 있다면 어떨까요? 당신은 아마 이것과 같은 것을 원할 것입니다 :

bool BinarySearchTree::Search(int val) {
  Node* current = root();
  while (current != NULL) {
    // Check if it's here
    if (val == current->value()) {
      return true;
    }
    if (val < current->value()) {
      current = current->left();
    } else {
      current = current->right();
    }
  }
  // Not found
  return false;
}

루프 불변량 : 각 루프의 시작 부분에서 "처리"해야하는 널 노드에 있습니다. 먼저 원하는 노드인지 확인하십시오. 그렇지 않은 경우, 분기를 만들고 루프가 분기가 "좋은"것인지 (예 : NULL)인지 결정하도록하십시오. 그런 다음 다음 루프 반복이 테스트를 처리하게 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top