Поиск двоичного дерева

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

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

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