StackOverFlowException в алгоритме BST

Question

Я пытался реализовать метод Contains в моем классе BSTree, который будет принимать значение, а затем проверять все узлы, чтобы увидеть, содержится ли оно в дереве. Я думаю, что алгоритм правильный, но я не знаю, почему я продолжаю получать StackOverFlowException в первом операторе if. Есть идеи?

public Boolean Contains(T item)
    {
      Node<T> node = root;
      return contains(root, item);
    }



    private Boolean contains(Node<T> node, T item)
    {
      if (item.CompareTo(root.Data) == 0)
      {
        return true;//return 0 if found
      }
      else
      {
        if (item.CompareTo(root.Data) > 0)
        {
          //root = node.Left;
          Node<T> left = root.Left;
          return(contains(root, item));
        }
        else
        {
          if (item.CompareTo(root.Data) < 0)
          {
            //root = node.Right;
            Node<T> right = root.Right;
            return(contains(root, item));
          }
          else
          {
            return false;//return 1 if not found
          }
        }        
      }
    }

Answer 1

Проблема с вашим кодом в том, что вы пропускаете неправильный узел в рекурсивных вызовах. Предположим, например, что ваш элемент меньше, чем все в дереве. Затем при первом рекурсивном вызове вы получите следующее утверждение:

Node<T> left = root.Left;
return(contains(root, item));

Это означает, что вы выполняете рекурсию на корне 1005 *, а не на левом дочернем элементе. Таким образом, на следующей итерации вы обнаружите, что элемент меньше правого дочернего элемента корня, и поэтому вы снова будете выполнять точно такой же оператор, рекурсивно вызывая одну и ту же функцию несколько раз, пока не закончится место в стеке.

Чтобы исправить это, вы должны изменить приведенный выше код на

Node<T> left = node.Left;
return(contains(left, item));

Это говорит о том, что нужно искать левое поддерево текущего узла, а не сам корневой узел. Точно так же вам нужно обновить соответствующий регистр для правой ветви.

Наконец, чтобы закончить, вам нужно добавить базовый регистр в вашу рекурсивную функцию, которая обрабатывает случай, когда дерево имеет значение null, либо потому, что вы вышли из дерева, либо дерево было пустым для начинается с. Я оставлю это как упражнение. : -)

Answer 2

Вам не нужна рекурсия.Вы можете просто выполнить итерацию, чтобы не получать StackOverflow, даже если у вас огромное дерево.

public Boolean Contains(T item) {
    Node<T> currentNode = root;

    while(currentNode != null) { // Or whatever you use to signal that there is no node.
        switch(item.CompareTo(currentNode.Data)) {
            case -1:
                currentNode = currentNode.Right;
                break;
            case 1:
                currentNode = currentNode.Left;
                break;
            default: // case 0
                return true;
        }
    }
    return false;
 }

Answer 3

ваша логика неверна. Он не перейдет к ложному утверждению возврата.

private Boolean contains(Node<T> node, T item)
    {
      if (item.CompareTo(root.Data) == 0)
      {
        return true;//return 0 if found
      }
      else///if 0 <> 
      {
        if (item.CompareTo(root.Data) > 0)  //if 0<
        {
          //root = node.Left;
          Node<T> left = root.Left;
          return(contains(root, item));
        }
        else  //if 0>
        {
          if (item.CompareTo(root.Data) < 0) if // 0>
          {
            //root = node.Right;
            Node<T> right = root.Right;
            return(contains(root, item));
          }
          else  // this will be not executed ever
          {
            return false;//return 1 if not found
          }
        }        
      }
    }