Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 06.02.2017, 18:32   #1
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию Поиск в бинарном дереве

Не получается организовать поиск в бинарном дереве по значению, а не по ключу.
Использую дерево в качестве примера переводчика, то-есть я ввожу англ. слово - ищет русское слово, помогите исправить метод поиска
Класс бинарного дерева:
Код:
package lab4;
 
import com.sun.corba.se.impl.oa.poa.ActiveObjectMap.Key;
 
public class BinaryTree {
 
    Node root;
 
    public void addNode(int key, String eng, String rus) {
 
        // Создает новый узел и инициализирует его с помощью конструктора
        Node newNode = new Node(key, eng, rus);
        // Если корня нет то он присваивается
        if (root == null) {
            root = newNode;
        } else {
            // Установить корень как node
            // и следить за текущим нодом
            Node focusNode = root;
            // Родитель для текущего нода
            Node parent;
            while (true) {
                // Корень является главным родителем таким образом мы начинаем обход
                // Тут родителю присваевается текушая нода
                parent = focusNode;
                // Проверка, если новый узел должен идти
                // Левая сторона родительского узла
                if (key < focusNode.key) {
                    //фокус на левый узел
                    focusNode = focusNode.leftChild;
                    // Если у левого узла нету детей
                    if (focusNode == null) {
                        // затем поместите новый узел слева от него
                        parent.leftChild = newNode;
                        return; //Все сделано
                    }
                } else { // В ином случае мы ставим узел на правую сторону
                    focusNode = focusNode.rightChild;
                    // Если у правого узла нету детей
                    if (focusNode == null) {
                        // затем поместите новый узел справа от него
                        parent.rightChild = newNode;
                        return; // Все сделано
                    }
                }
            }
        }
    }
 
    // Поиск узла
    public Node findNode(String eng) {
        // Начать с верхушки дерева
        Node focusNode = root;
        // Пока мы не нашли узел
        // Продолжать поиски
        while (focusNode.eng != eng) {
            int key = 0;
            // Если мы должны искать влево
            if (key < focusNode.key) {
                // Сдвиг фокуса узла к левому ребенку
                focusNode = focusNode.leftChild;
            } else {
                // Сдвиг фокуса узла к правому ребенку
                focusNode = focusNode.rightChild;
            }
            // Узел не найден
            if (focusNode == null)
                return null;
        }
        return focusNode;
    }
}
 
class Node {
    int key;
    String eng;
    String rus;
    Node leftChild;
    Node rightChild;
    
    Node(int key, String eng, String rus) {
        this.key = key;
        this.eng = eng;
        this.rus = rus;
    }
 
    public String toString() {
        return eng + " ----> " + rus;
        /*
         * return name + " has the key " + key + "\nLeft Child: " + leftChild +
         * "\nRight Child: " + rightChild + "\n";
         */
    }
}
Класс Main
Код:
package lab4;
 
public class Main {
 
    public static void main(String[] args){
 
        BinaryTree theTree = new BinaryTree();
        theTree.addNode(1, "Apple", "Яблоко");
        theTree.addNode(2, "Dog", "Собака");
        theTree.addNode(3, "Cat", "Кошка");
        theTree.addNode(4, "Hat", "Шляпа");
        theTree.addNode(5, "Black", "Черный");
        theTree.addNode(6, "Player", "Игрок");
        
        System.out.println(theTree.findNode("Apple"));
    }
}
Заранее спасибо за помощь
Max00766 вне форума Ответить с цитированием
Старый 06.02.2017, 20:03   #2
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

Выложи весь проект.
ura_111 вне форума Ответить с цитированием
Старый 06.02.2017, 20:27   #3
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Цитата:
Сообщение от ura_111 Посмотреть сообщение
Выложи весь проект.
Вот, в проекте реализовал разные функции для работы с деревом, в задании вообще указан поиск по ключу, я его и сделал (точнее нашел метод и допилил ), но хочется сделать что бы именно по словам искало
lab4.rar
Max00766 вне форума Ответить с цитированием
Старый 07.02.2017, 00:59   #4
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

Я заметил, что у тебя заполняется только "право"... Ну всё, вооружившись этим знанием, я вроде, забацал:
Код:
    // Поиск узла
    public Node findNode(String key) {
        // Начать с верхушки дерева
        Node focusNode = root;
        // Пока мы не нашли узел
        // Продолжать поиски
        while (true) {
            // Узел найден
            if (focusNode.eng== key) {
                return focusNode;
            }

            focusNode = focusNode.rightChild;

            // Узел не найден
            if (focusNode.rightChild== null)
                return null;
        }
    }
Вот результат:

0.jpg

Но остаётся вопрос: а "лево" зачем?. И чем тогда отличается "дерево всегда с справой развилкой" от простого массива? (кстате, а в массиве этот поиск занял бы ровно 3-ри строчки: for+if+break; И остальные функции тоже упростились бы...).
1.jpg

p.s.1: сложно искать узел дерева по английскому значению, если это значение никак не участвует в формировании этого самого дерева... Разве что обычный перебор применить; но для него нужно хранить знания по всем предыдущим развилкам, чтобы, в случае не удачи, можно было вернуться назад (на несколько позиций вверх) и повернуть в другую ветвь... Но для этого понадобится городить массив (bool-кий) - но ведь это бред: к дереву ещё и логистический массив (ведь дерево само по себе это логистика)... Хотя, если у тебя только правосторонее дерево, тогда, то что написал выше, то и правильно... Подумай: в случае всевозможных комбинаций функций "добавить / удалить" возможно ли появления "левосторонней развилки"? Или нет?
p.s.2: когда я в первый раз прочитал у тебя "...пример переводчика", то сразу подумал не о "двух разветвлениях", а о "двадцать шести разветвлений" (или сколько там английских букв?). Ну вот, например, часть словаря в виде дерева (сопоставь "переходы" со "словами в квадратиках"):

2.jpg

Тогда и поиск был бы такой (для примера слово "attach"):

3.jpg

Последний раз редактировалось ura_111; 07.02.2017 в 01:33.
ura_111 вне форума Ответить с цитированием
Старый 07.02.2017, 11:26   #5
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Цитата:
Сообщение от ura_111 Посмотреть сообщение
Я заметил, что у тебя заполняется только "право"... Ну всё, вооружившись этим знанием, я вроде, забацал:
Код:
    // Поиск узла
    public Node findNode(String key) {
        // Начать с верхушки дерева
        Node focusNode = root;
        // Пока мы не нашли узел
        // Продолжать поиски
        while (true) {
            // Узел найден
            if (focusNode.eng== key) {
                return focusNode;
            }

            focusNode = focusNode.rightChild;

            // Узел не найден
            if (focusNode.rightChild== null)
                return null;
        }
    }
Вот результат:

Вложение 86099

Но остаётся вопрос: а "лево" зачем?. И чем тогда отличается "дерево всегда с справой развилкой" от простого массива? (кстате, а в массиве этот поиск занял бы ровно 3-ри строчки: for+if+break; И остальные функции тоже упростились бы...).
Вложение 86100

p.s.1: сложно искать узел дерева по английскому значению, если это значение никак не участвует в формировании этого самого дерева... Разве что обычный перебор применить; но для него нужно хранить знания по всем предыдущим развилкам, чтобы, в случае не удачи, можно было вернуться назад (на несколько позиций вверх) и повернуть в другую ветвь... Но для этого понадобится городить массив (bool-кий) - но ведь это бред: к дереву ещё и логистический массив (ведь дерево само по себе это логистика)... Хотя, если у тебя только правосторонее дерево, тогда, то что написал выше, то и правильно... Подумай: в случае всевозможных комбинаций функций "добавить / удалить" возможно ли появления "левосторонней развилки"? Или нет?
p.s.2: когда я в первый раз прочитал у тебя "...пример переводчика", то сразу подумал не о "двух разветвлениях", а о "двадцать шести разветвлений" (или сколько там английских букв?). Ну вот, например, часть словаря в виде дерева (сопоставь "переходы" со "словами в квадратиках"):

Вложение 86101

Тогда и поиск был бы такой (для примера слово "attach"):

Вложение 86102
Спасибо большое
Просто раньше как-то был на алгоритмы и структуры подзабил, а теперь когда это пригодилось пришлось сидеть все учить, вроде и без проблем понял как бинарное дерево работает, ну а с реализацией немного запарился, буду разбираться, еще раз спасибо за Вашу помощь
Max00766 вне форума Ответить с цитированием
Старый 07.02.2017, 12:45   #6
ura_111
Участник клуба
 
Регистрация: 14.05.2016
Сообщений: 1,793
По умолчанию

Я тут вычитал, что простое сравнение строк ("==") в некоторых средах не работает:
0.jpg


Если у тебя будет подобное - замени на "equals".

Последний раз редактировалось ura_111; 07.02.2017 в 12:51.
ura_111 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Prolog братья в бинарном дереве Gorgetr Помощь студентам 11 29.05.2013 09:07
Указатель на родителя в бинарном дереве Green Gin Общие вопросы C/C++ 8 01.04.2012 18:14
удаление элемента в бинарном дереве Kukurudza Общие вопросы C/C++ 1 26.06.2011 22:51
Поиск в бинарном дереве не по ключу lebrosha Помощь студентам 2 26.05.2009 15:32
Удаление вершины в бинарном дереве lebrosha Помощь студентам 2 24.05.2009 13:51