Удаление элемента из двоичного бинарного дерева поиска - C#

Узнай цену своей работы

Формулировка задачи:

Здравствуйте! Подскажите пожалуйста, как удалить элемент из двоичного бинарного дерева поиска, если имеются как левое, так и правое ответвление(очень желательно, что бы была теория и сам алгоритм)? Я уже читал теорию в другой похожей теме, но не понял её(именно ту часть, где говорится о том, что делать, если есть два ответвления). Смотрел пример на C, переписал под C#-в итоге, нужный элемент не удалился, а при последующей попытке удалить элемент с одним ответвлением получал Exception("Ссылка не ссылается на экземпляр объекта")... Вот кот, который у меня есть на данный момент(проверял-вроде бы то, что готово-то работает правильно(во всяком случае-согласно той теории, которую я читал)):
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;
            }
Я читал здесь, что нужно двигаться в первой ветви до дна в левую часть, и присвоить parent левой части удаляемого элемента ссылке на левое дно Right... Пытался реализовать этот алгоритм-ничего хорошего не вышло... Вот, "не рабочий алгоритм":
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;
P.S. Сразу пишу в Windows Application варианте. Таблицу DataGridView после удаления элемента всю обновляю(т.е. сразу получаю список всех элементов, после чего именно из списка получаю всё обратно в DataGridView). Все Exception перехватываю блоком Try/Catch. Обходить мне моё дерево по заданию надо через рекурсию. Ну, я и обхожу... Вызываю этот метод удаления лишь в процессе поиска нужного элемента.

Решение задачи: «Удаление элемента из двоичного бинарного дерева поиска»

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);
    }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.727 из 5
Похожие ответы