StackOverflowError при реализации метода поиска в двоичном дереве в Java ⇐ JAVA

[Anonymous]

Я работаю над реализацией метода find(int v) в двоичном дереве на Java, где мне нужно найти узел, содержащий заданное значение v. Метод должен возвращать узел, если он найден, в противном случае он должен возвращать ноль. . Ниже приведен код, который я реализовал:

Код: Выделить всё

class Node {
Node left, right;
int value;

public Node find(int v) {
if (this == null) return null;
if (this.value == v) return this;
Node found = (left != null) ? left.find(v) : null;
if (found == null) {
found = (right != null) ? right.find(v) : null;
}
return found;
}
}

Однако при запуске кода я сталкиваюсь с ошибкой StackOverflowError. Я подозреваю, что это связано с рекурсивными вызовами, но не знаю, почему это происходит и как это исправить.
Что я пробовал:
Проверка того, что дерево построено правильно и не содержит циклов.
Проверка того, имеют ли левый и правый дочерние элементы значение NULL, прежде чем выполнять рекурсивные вызовы.
Сообщение об ошибке:

Код: Выделить всё

Exception in thread "main" java.lang.StackOverflowError

Вопросы:
Почему я сталкиваюсь с ошибкой StackOverflowError в моей текущей реализации?
Как я могу изменить свой метод поиска, чтобы избежать этой ошибки ?
Существуют ли какие-либо рекомендации по реализации методов поиска в двоичных деревьях для предотвращения таких ошибок?
Будем очень благодарны за любую помощь или идеи!< /p>
Постановка задачи:
Дерево состоит из узлов, которые подчиняются следующим правилам:

• Каждый узел содержит значение, соответствующее целому числу.
• За исключением корневого узла, каждый узел имеет ровно один другой узел,
  ссылающийся на него. >
• Узел не может быть левым или правым дочерним элементом более чем одного узла.
• Если у узла нет левого или правого дочернего элемента, то его ссылка
  null.
• Значение левого дочернего узла любого узла меньше значения
  узла, а значение правого дочернего узла любого узла больше илиравен значению узла.

Вот пример дерева, которое следует этим правилам (корень – 9):

Код: Выделить всё

9
/    \
5      13
/  \    /   \
1    8  12   17

Вопрос:
Реализуйте в классе Node метод find(int x), который возвращает узел, содержащий значение x. Если этот узел не существует, метод должен возвращать значение null.
Ограничения:
Высота дерева (расстояние между самым дальним узлом и корень) составляет от 0 до 100 000 узлов.
Сведите к минимуму использование оперативной памяти.

Подробнее здесь: https://stackoverflow.com/questions/790 ... ee-in-java