Рекурсивный поиск по двоичному дереву - PullRequest
Новая
       2

Рекурсивный поиск по двоичному дереву

0 голосов
/ 07 августа 2011

Может ли кто-нибудь помочь мне отследить этот кусок кода, если он правильный или неправильный. Сейчас я изучаю рекурсию. 

boolean search(Element element) {
    Element c=first;
    if(c==null)
        return false;
    else if(element.asset < c.asset)
        if(c.left==null)
            return false;
        else
            return search(c.left);
    else if(element.data>c.data)
        if(c.right==null)
            return false;
        else
            return search(c.right);
     else  
         return element.asset==c.asset;
}

Ответы [ 3 ]

3 голосов
/ 07 августа 2011

отсутствует условие остановки. Вы должны проверить, если t.left == null, или вы получите NullPointerException. также вы должны вернуть t.left.isExist(..) ИЛИ t.right.isExist(...), а не isExist [вы захотите вызвать этот метод для сына]

В настоящее время эта версия попадет в бесконечный цикл - потому что вы всегда будете проверять один и тот же корневой узел.

1 голос
/ 07 августа 2011

Ваш код не симметричен.

для одной стороны вы звоните isExist(t.left), для другой - isExist(a.right)

Возможно, вы хотите позвонить t.left.isExist(a) и t.right.isExist(a), но это чисто умозрительно, так как у вас нет полной SSCCE , на которую мы могли бы взглянуть.

0 голосов
/ 09 августа 2011

Это синтаксически правильная Java.Но я не понимаю, как он мог бы делать то, что вы намеревались.

Похоже, что параметр 'element' - это то, что вы ищете, а первое поле в текущем классе - корень.двоичного дерева.

Неясно, является ли ключ для двоичного дерева и поиска (в классе Element) «активом» или «данными».Тест «меньше чем» использует «актив», а тест «больше чем» использует «данные».Вполне вероятно, что обе строки должны использовать одно и то же поле.Может случиться так, что одно из этих двух полей ('актив' или 'данные') должно не быть упомянуто в этом методе вообще.Может быть, последняя строка метода должна быть просто «вернуть истину»?

(я подозреваю, что ответы «условие остановки» и «код не симметричны» выше оба неверны. НоЯ могу ошибаться: трудно сказать только с указанным кодом.)

Я согласен, что бесконечный цикл вероятен: я подозреваю, что вам нужно создать вторую функцию поиска, которая принимает дваПараметры элемента - один для поиска (например, текущий параметр элемента), а другой - следующий для поиска элемент - эквивалент текущей локальной переменной 'c'.Я бы сделал рефакторинг «Извлечь метод» для всего в теле текущего метода «поиска», кроме первой строки, а затем изменил бы два рекурсивных вызова, чтобы использовать новый метод.

(Некоторыеэто спекулятивный вопрос, основанный на том, что я угадал, что вы хотите или намереваетесь, учитывая ограниченную информацию. Поэтому я могу, конечно, ошибаться.)

...