Бинарный поиск в Java - что не так с моим кодом

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

Это моё текущее дерево
10
/ \
24 30
/ \
3 15
/
8



Это мой код методов:

private BNode search(BNode theRootNode, int value) {
BNode node = theRootNode;
if (node == null) { 
    return null;
} else {
    if  (value == node.value) 
        return node;
    else {
        if (node.left != null)
            node = search(node.left, value);
        if (node.right != null)
            node = search(node.right, value);
        return node;
    }
}

}

public BNode find(int value) {
    return  search(root, value);

}

Когда у него нет левой стороны (элемент 8), я хочу, чтобы он всплыл до элемента 10, а затем попробуйте правую сторону (элемент 30)

Источник

2 ответа

Решение

Вы делаете основной поиск в глубину:

Теперь я вижу, что вы возвращаете текущий узел в 2 случаях:

  1. Это откровенный матч
  2. Ничего не подходит

Похоже, логический недостаток.

 if  (value == node.value)  //Lets say search element is 9 and node=8, false
        return node;
    else {
        if (node.left != null)               //false
            node = search(node.left, value);      
        if (node.right != null)              //false
            node = search(node.right, value);
        return node;                          // return node=8...what?
    }

Я предлагаю сделать шаг назад и переосмыслить, что вы пытаетесь сделать и как. Это не бинарный поиск, потому что дерево - это просто двоичное дерево, а не двоичное дерево поиска.

Источник

JFYI - это не бинарный поиск, а дерево, которое вы указали в своем примере, не является бинарным деревом поиска.
http://en.wikipedia.org/wiki/Binary_search_tree

То, что вы пытаетесь сделать, это пройти через все узлы в дереве и найти элемент. Это будет O(n) искать а не O(lgn) что вы должны получить из бинарного поиска в бинарном дереве поиска.
Причина, по которой ваш код возвращает узел 8, состоит в том, что ваша рекурсия идет вниз по левой ветви и и возвращает первый найденный лист.
Увидимся код:

if (node.left != null)
    node = search(node.left, value);
if (node.right != null)
    node = search(node.right, value);
return node;

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

Источник
Другие вопросы по тегам