Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.68/34: Рейтинг темы: голосов - 34, средняя оценка - 4.68
1 / 1 / 1
Регистрация: 27.04.2017
Сообщений: 18

Удаление элемента из бинарного дерева поиска (bst)

26.10.2018, 03:27. Показов 6543. Ответов 3

Студворк — интернет-сервис помощи студентам
Есть структура данных bst с методом delete (и некоторыми другими, не имеющими отношения к данной проблеме).
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class BinarySearchTree {
 
    public static class Node {
        Node left;
        Node right;
        int value;
 
        Node(int value) {
            this.value = value;
        }
    }
    public Node root;
 
   public void printAll(Node node) {
        if (node != null) {
            System.out.println(node.value);
            if (node.left!=null) {
                System.out.println("Left children (node " + node.value +"): ");
                printAll(node.left);
            }
            if (node.right!=null) {
                System.out.println("Right children (node " + node.value +"): ");
                printAll(node.right);
            }
        }
    }
 
    public void delete(Node current, Node delNode) {
        if (root == null) {
return; 
}
        else if (delNode.value < current.value) {
            if (current.left != null) {
                delete(current.left, delNode);
            } else {
                return;
            }
        } else if (delNode.value > current.value) {
            if (current.right != null) {
                delete(current.right, delNode);
            } else {
                return;
            }
        } else {
            if (current.right == null && current.left == null) {
                current = null;
            }
        }
        return;
        }
}
Проблема настигла меня в методе delete в строке
Java
1
2
3
 if (current.right == null && current.left == null) {
                current = null;
            }
При выводе дерева методом printAll заметил, что необходимый элемент не удаляется, и дерево никак не меняется.
Если заменить на
Java
1
current.value = 0
,
то будет отображено дерево со значением удалённого элемента 0, т.о. проблема именно в присваивании объекту current значения null.

P.S. Да, условие удаления прописано только для листьев дерева. Метод не доработан до конца, сначала хочу решить возникшую проблему, поскольку в других случаях она так же возникнет.
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
26.10.2018, 03:27
Ответы с готовыми решениями:

Некорректное удаление элемента бинарного дерева поиска
Задача состоит в том, чтобы удалить максимальный в левом поддереве элемент и все его порожденные элементы. Я нахожу этот элемент и...

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

Удаление нечетных чисел из дерева бинарного поиска
Задача: Удалить нечетные числа из дерева бинарного поиска. Вообщем, ошибка в функции удаления нечетных. Как я понял я выхожу за границы...

3
 Аватар для Aviz__
2742 / 2051 / 507
Регистрация: 17.02.2014
Сообщений: 9,472
26.10.2018, 10:56
Цитата Сообщение от bormash Посмотреть сообщение
При выводе дерева методом printAll
лучше использовать https://www.cyberforum.ru/java/thread2250765.html
0
958 / 577 / 136
Регистрация: 23.05.2012
Сообщений: 7,364
26.10.2018, 16:47
Лучший ответ Сообщение было отмечено Black Fregat как решение

Решение

Цитата Сообщение от bormash Посмотреть сообщение
public void delete(Node current, Node delNode)
Переменные в Java передаются по значению. Поэтому то, что Вы меняете значение ссылки current в теле метода из вне никак не видно.
У Вас в классе хранится root. Передавайте в метод delete что именно надо удалить, ищите удаляемый элемент от root и удаляйте.
0
75 / 61 / 29
Регистрация: 20.04.2015
Сообщений: 415
26.10.2018, 18:33
у тебя в классе только метод удаления а метод добавления элемента где? и выложи тестирование как ты тестишь .Про отладку тебе хорошо посоветовали ты знаешь свой код и сразу увидишь ошибку.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
26.10.2018, 18:33
Помогаю со студенческими работами здесь

Удаление элементов из бинарного дерева (не дерево поиска)
Задание заключается в создании бинарного дерева, из букв введенной строки, обходе дерева и удалении согласных букв из дерева. проблема...

удаление элемента бинарного дерева
как удалить элемент бинарного дерева,имеющий 2 потомка?(например дерево (2)-(7 и 0)-(4 и 10),порядок вхождения 2,7,4,10,0 удалить надо...

Удаление элемента из бинарного дерева
Ругается компилятор в Visual Studio при выполнении кода удаления элемента, а именно в том месте, где нужно удалить элемент с двумя...

Удаление элемента из бинарного дерева
в программе выполняется пару ф-й, не работает удаление элемента (в меню пункт 1), должен удалить узел где длина кода более 5, при попытке...

Реализовать удаление элемента бинарного дерева
Подскажите пожалуйста, нужен метод, который удаляет элемент( и возвращает этот элемент) из бинарного дерева. Есть набросок, но незнаю как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru