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

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

26.10.2018, 03:27. Просмотров 2531. Ответов 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.10.2018, 03:27
Ответы с готовыми решениями:

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

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

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

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

3
1688 / 1324 / 334
Регистрация: 17.02.2014
Сообщений: 7,006
26.10.2018, 10:56 2
Цитата Сообщение от bormash Посмотреть сообщение
При выводе дерева методом printAll
лучше использовать https://www.cyberforum.ru/java/thread2250765.html
0
955 / 574 / 136
Регистрация: 23.05.2012
Сообщений: 7,370
26.10.2018, 16:47 3
Лучший ответ Сообщение было отмечено 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 4
у тебя в классе только метод удаления а метод добавления элемента где? и выложи тестирование как ты тестишь .Про отладку тебе хорошо посоветовали ты знаешь свой код и сразу увидишь ошибку.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.10.2018, 18:33

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.