Рекурсивное двоичное дерево Java

Question

Добро пожаловать! У меня есть рекурсивный публичный статический метод с наименьшим значением, который принимает узел дерева (исходное двоичное дерево, а не дерево поиска) и параметр int, который возвращает, если все значения в дереве меньше целого. Таким образом, я хотел бы использовать public class TN { public int value; public TN left, right; public TN(int v, TN l, TN r) {value = v; left = l; right = r;} } Итак, мой метод будет выглядеть следующим образом:

public static boolean less(TN s, int toFind){ 
if (s == null) 
    return true; 
else{ 
if(s.value <= toFind) 
    return less(s.left, toFind) && less(s.right, toFind); // right here do I return true? or do I have to somehow recall recursively 
else 
    return false; 
} 

мне было интересно, если это было правильно, или я что-то отсутствует ??? Должен ли я возвращать истину и ложь?

Answer 1

return less(s, toFind); 

должно быть:

return less(s.left, toFind) && less(s.right, toFind); 

Я не знаю, почему функция является статическим.

Как упоминалось ранее, ваша первая часть должна быть просто:

if (s == null) return true; 

(EDIT:. Это позволит получить верный результат, когда все узлы отвечают условию У вас есть == там, что должно быть a <). EDIT: Хорошо, у вас много проблем, чем только те, о которых я говорил. Вам необходимо логически выполнить свой код.

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

Answer 2

Во-первых, if (s = null) должен быть if (s == null), поскольку вы проводите сравнение, не устанавливая значение s на null.

Заявление return less(null, toFind); продолжает вызывать ваш метод - вы переполните свой стек.

Answer 3

Есть намного более элегантные, OO способы написать это. Моя рекомендация заключалась бы в том, чтобы сделать less() нестатической функцией-членом класса TN. Таким образом, если корневой узел дерева называется root, вы просто вызываете root.less(). Затем каждый звонок до less() вызывает left.less() и right.less().

Поскольку вы отправили пример кода, который даже не был скомпилирован, мне интересно, используете ли вы IDE или даже пытались скомпилировать свой класс, используя javac. Я настоятельно рекомендую получить Eclipse, Netbeans или другую среду IDE, если вы новичок в Java.

Answer 4

Обратите внимание, что ваша функция никогда не может вернуть true, потому что каждый раз, когда вы завершаете рекурсию, вы возвращаете false? И проблема в вашей первой проверке. Вы говорите, что «все значения в дереве меньше целого». Ну, в пустом дереве все значения (которых их нет) действительно меньше любого целого числа, поэтому в этом случае вы должны вернуть true.

Кроме того, хотя вы говорите «меньше», вы сравниваете это равенство, поэтому вы фактически проверяете, равны ли все значения целым, а не меньше.