-
12-09-2019 - |
문제
나는 특정 값에 대해 이진 트리를 검색하기 위해 반복적 인 기능을 작성하고 있습니다. 클래스를 제네릭하는 방법에 들어가기 전까지는 서명 된 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)인지 결정하도록하십시오. 그런 다음 다음 루프 반복이 테스트를 처리하게 할 수 있습니다.