поиск двоичного дерева - PullRequest
Новая
       32

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

0 голосов
/ 11 июля 2009

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

Предположим, что мой класс - 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 предложить какие-либо идеи?

Ответы [ 3 ]

2 голосов
/ 11 июля 2009

Я думаю, что вы должны тестировать, если 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;
}
1 голос
/ 11 июля 2009

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

while (next != NULL)?

0 голосов
/ 11 июля 2009

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

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

...