Я хочу написать метод, который удаляет узел из двоичного дерева поиска.BST удалить метод узла «отключает» остальную часть дерева
Это мой метод:
public void remove(Node node)
\t //Removes a given node and puts one of the nodes below it in its place until it reaches the end
\t {
\t \t
\t \t if (node.left != null) //If the node to the left is not empty
\t \t {
\t \t \t node.value = node.left.value; //Moves up the left node to take its place
\t \t \t remove(node.left); //Goes to the next node
\t \t \t if (node.left.right == null && node.left.left == null)
\t \t \t \t node.left = null; //Removes the last node at the end of the tree after moving it up
\t \t }
\t \t else if (node.right != null)
\t \t {
\t \t \t node.value = node.right.value; //Moves up the left node to take its place
\t \t \t remove(node.right); //Goes to the next node
\t \t \t if (node.right.left == null && node.right.right == null)
\t \t \t \t node.right = null; //Removes the last node at the end of the tree after moving it up
\t \t \t
\t \t } \t
\t \t
\t }Проблема заключается в том, что работает только в некоторых случаях.
Допустим, например, что я вхожу 60, 70, 65. (корневой узел 50) Дерево должно выглядеть как
50
/\
60
/ \
70
/\
65
Позволяет затем сказать, я выбираю, чтобы удалить 60. Это, кажется, работает штраф сначала. Однако, если я затем запустил свой метод поиска, который, я надеюсь, вернет, что 70 не имеет узлов ни в одном из указателей.
Что я предполагаю, так это то, что 70 устанавливается в null до 65 может быть перемещено вверх. И поскольку 65 технически больше не подключены к дереву, метод поиска не может его найти.
Так что-то вроде этого:
50
/\
70
/ \
/\
65
Проблема заключается в том, я не понимаю, как это могло произойти. Тем более, что он должен установить узел в нуль, если оба его указатели указывают на нулевое значение, в связи с, если заявления
if (node.left.right == null && node.left.left == null)
node.left = null;
и
if (node.right.left == null && node.right.right == null)
node.right = null;
Кроме того, если первый, если заявление не соответствует действительности (если оставлено ! = null), не следует ли просто продолжать «else» (и удалить правильный)?
Любые предложения или советы приветствуются.
Сделайте себе одолжение и отделить код BST из кода Swing. Напишите модульные тесты для вашего BST и убедитесь, что он работает правильно, затем подключите его к интерфейсу. –
Я не знаю, как сделать дерево здесь, но возьмите свое оригинальное дерево и положите 65, где было 60. Я не думаю, что у вас есть дерево, как вы думаете. – Marichyasana
Дерево примера Марричасаны - это правильный BST; тот, который был бы результатом вашей модификации, не является. – Matt