Удаление элемента из двоичного бинарного дерева поиска - C#
Формулировка задачи:
Здравствуйте!
Подскажите пожалуйста, как удалить элемент из двоичного бинарного дерева поиска, если имеются как левое, так и правое ответвление(очень желательно, что бы была теория и сам алгоритм)?
Я уже читал теорию в другой похожей теме, но не понял её(именно ту часть, где говорится о том, что делать, если есть два ответвления). Смотрел пример на C, переписал под C#-в итоге, нужный элемент не удалился, а при последующей попытке удалить элемент с одним ответвлением получал Exception("Ссылка не ссылается на экземпляр объекта")...
Вот кот, который у меня есть на данный момент(проверял-вроде бы то, что готово-то работает правильно(во всяком случае-согласно той теории, которую я читал)):
Я читал здесь, что нужно двигаться в первой ветви до дна в левую часть, и присвоить parent левой части удаляемого элемента ссылке на левое дно Right... Пытался реализовать этот алгоритм-ничего хорошего не вышло...
Вот, "не рабочий алгоритм":
P.S. Сразу пишу в Windows Application варианте. Таблицу DataGridView после удаления элемента всю обновляю(т.е. сразу получаю список всех элементов, после чего именно из списка получаю всё обратно в DataGridView). Все Exception перехватываю блоком Try/Catch.
Обходить мне моё дерево по заданию надо через рекурсию. Ну, я и обхожу... Вызываю этот метод удаления лишь в процессе поиска нужного элемента.
public BinaryTree<TYPE> DeleteData(TYPE ValueKey) { BinaryTree<TYPE> ThisData = this; if (ThisData.Value == null) throw new Exception("Невозможно удалить элемент из пустого дерева"); else { Int32 CompareToResult = ThisData.Value.CompareTo(ValueKey); if (CompareToResult == 0) { if (ThisData.Right == null && ThisData.Left == null) { ThisData = ThisData.Parrent; { if (ThisData.Value.CompareTo(ValueKey) > 0) ThisData.Left = null; else if (ThisData.Value.CompareTo(ValueKey) < 0) ThisData.Right = null; } } else if (ThisData.Right == null && ThisData.Left != null) { ThisData = ThisData.Parrent; { if (ThisData.Value.CompareTo(ValueKey) > 0) ThisData.Left = ThisData.Left.Left; else if (ThisData.Value.CompareTo(ValueKey) < 0) ThisData.Right = ThisData.Right.Left; } } else if (ThisData.Right != null && ThisData.Left == null) { ThisData = ThisData.Parrent; { if (ThisData.Value.CompareTo(ValueKey) > 0) ThisData.Left = ThisData.Left.Right; else if (ThisData.Value.CompareTo(ValueKey) < 0) ThisData.Right = ThisData.Right.Right; } } else if (ThisData.Right != null && ThisData.Left != null) { } } else if (CompareToResult > 0) ThisData.Left.DeleteData(ValueKey); else if (CompareToResult < 0) ThisData.Right.DeleteData(ValueKey); } while (ThisData.Parrent != null) ThisData = ThisData.Parrent; return ThisData; }
BinaryTree<TYPE> NRight = ThisData.Right; while (NRight.Left != null) NRight = NRight.Left; BinaryTree<TYPE> NLeft = ThisData.Left; NLeft.Parrent = NRight; while (NLeft.Parrent != null) NLeft = NLeft.Parrent; ThisData = NLeft;
Решение задачи: «Удаление элемента из двоичного бинарного дерева поиска»
textual
Листинг программы
public void delete(int key) { if (this._key == key)//Если текущий элемент является удаляемым элементом { //Сперва, рассмотрим сценарий, где у нас нету ответвлений(удаляем лист, а не ветвь) if (this._left == null && this._right == null) { if (this._up != null) { binaryTree<T> up = this._up; if (up._key > key) up._left = null; else up._right = null; } else System.out.println("Невозможно удалить единственный элемент дерева. Воспользуйтесь функцией замены элемента"); } //После этого, рассмотрим сценарий, где у нас есть хотя бы одно ответвление else if ((this._left != null && this._right == null) || (this._right != null && this._left == null)) { binaryTree<T> _backup = (this._left != null ? this._left : this._right); binaryTree<T> _backup_up = this._up; if (_backup_up._key > key) { _backup_up._left = _backup; _backup._up = _backup_up; } else if (_backup_up._key < key) { _backup_up._right = _backup; _backup._up = _backup_up; } } //И в конце, рассмотрим сценарий, где у нас оба ответвления присутствуют/не пустые else if (this._left != null && this._right != null) { binaryTree<T> _backup = this._right; while (_backup._left != null) _backup = _backup._left; int _backup_key = _backup._key; T _backup_value = _backup._value; this.delete(_backup_key); this._key = _backup_key; this._value = _backup_value; } } else if (this._key > key && this._left != null) this._left.delete(key); else if (this._key < key && this._right != null) this._right.delete(key); }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д