0
В настоящее время я пишу метод, который удаляет заданное значение из двоичного дерева поиска. Однако, когда я его вызываю, он удаляет указанное значение, но затем дублирует каждое другое значение. Понятия не имею почему. Пожалуйста, скажите мне, что не так. Существует два метода: один, который находит элементы, а другой - его удаление. Вот один, который находит этот элемент ...Удаление элементов из двоичного дерева поиска
public static TreeNode delete(TreeNode t, Comparable x, TreeDisplay display)
{
if(x.compareTo(t.getValue()) > 0)
{
display.visit(t);
t.setRight(delete(t.getRight(), x, display));
}
else if (x.compareTo(t.getValue()) < 0)
{
display.visit(t);
t.setLeft(delete(t.getLeft(), x, display));
}
else
{
t = deleteNode(t, display);
}
return t;
Это метод, который удаляет значение
private static TreeNode deleteNode(TreeNode t, TreeDisplay display)
{
if (t.getRight()!=null)
{
TreeNode right = t.getRight();
TreeNode max = (TreeNode)TreeUtil.leftmost(right);
TreeNode previous = null;
while (right.getLeft()!=null&&right.getLeft().getLeft()!=null)
{
right = right.getLeft();
}
t.setValue(max.getValue());
if (max.getRight()==null)
{
right.setLeft(null);
}
else
{
right.setLeft(max.getRight());
}
}
else if (t.getLeft() !=null)
{
TreeNode left = t.getLeft();
TreeNode max = (TreeNode)TreeUtil.rightmost(left);
while(left.getRight()!=null &&left.getRight().getRight()!=null)
{
left = left.getRight();
}
t.setValue(max.getValue());
if (max.getLeft()==null)
{
left.setRight(null);
}
else
{
left.setRight(max.getLeft());
}
}
else
{
t = null;
}
return t;
}
Спасибо заранее!
В этом случае отладчик может пригодиться. Вы можете выполнить выполнение кода и посмотреть, что он на самом деле делает неправильно. Также в deleteNode вы не устанавливаете новое значение для возврата. Вы возвращаете t, но t никогда не изменяется. например там должно быть '' 't = t.getLeft()' '' где-то. – kristianp
С самого начала это похоже, что вы ненужно делаете это слишком сложным. Получите соответствующий узел, похоже, вы знаете, как это сделать. Затем просто удалите узел maxLeft или minRight. Похоже, слишком много проверок и изменений для чего-то настолько простого. – ChiefTwoPencils