поиск в бинарном дереве

Question

Я пишу итеративную функцию для поиска определенного значения в двоичном дереве.Это локализовано для целых чисел со знаком, пока я не узнаю, как обобщать классы.

Предположим, что мой класс — BinarySearchTree и у него есть указатель на корневой узел дерева.Также предположим, что узлы вставляются с помощью функции вставки и имеют указатели на двух дочерних узлов.Вот сильно сокращенная версия структуры Node:

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

Итак, вы можете смело предположить, что указатели uninit узла будут NULL.

Вот мой код:

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) Если у next нет дочерних элементов, оба будут равны нулю, и я преждевременно выйду из цикла (я никогда не буду сверять искомое значение со значением next).

2) Если у next есть один дочерний элемент, но данные, которые вы ищете, должны находиться на пустой стороне дерева, параметру next будет присвоено значение 0, и он снова зациклится, сравнивая next (который равен 0) слева и справа. деревья как while(0->left()), что приводит к неопределенному поведению.

Мне сказали, что решение обеих проблем заключается в условии цикла, но я не вижу, что можно сделать, чтобы легко исправить ситуацию.Может ли сообщество Stack Overflow предложить какие-либо идеи?

Answer 1

Я думаю, вам следует проверить, не имеет ли значение next в вашем цикле NULL, например:

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

Answer 2

Попробуй это:

while (next != NULL) ?

Answer 3

Прежде всего, я не понимаю, почему вы возвращаете 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;
}

Обратите внимание, что инвариант цикла:в начале каждого цикла вы находитесь на ненулевом узле, который вам нужно «обработать».Сначала проверьте, тот ли это узел, который вам нужен.Если нет, создайте ветвь и позвольте циклу решить, была ли ветвь «хорошей» (т. е. не нулевой).Затем вы позволите следующей итерации цикла позаботиться о тестировании.