Удаление узла бинарного дерева код удаления узла дерева

Как удалить узел в дереве C++?

Помогите реализовать дерево неспециального типа, которое пока что умеет создаваться и выводиться. Нужно, чтобы узел дерева можно было удалить (по ключу). У меня не получается настроить связи с родительским узлом из-за этого и проблемы Метод удаления: если у узла нет потомков, то он удаляется. Если у узла есть хотя бы 1 потомок, то узел заменяется его крайним левым дочерним узлом.

#include using namespace std; struct Node < int key = NULL; //ключ int //индекс int level = 0; //уровень в иерархии Node* parent = nullptr; //указатель на родителя Node** son = nullptr; //массив указателей на сыновей Node* leftmost_child = nullptr; int count_son = 0; //количество сыновей >; Node* createTree(Node* node, int id, int level) < node->id = id; node->level = level; cout level id > node->count_son >> node->key; node->son = new Node*[node->count_son]; level++; for (int i = 0; i < node->count_son; i++) < node->son[i] = new Node; node->son[i]->id = id + i; node->son[i]->level = level; > for (int i = 0; i < node->count_son; i++) createTree(node->son[i], id + i, level); return node; > void printTree(Node* node) < if (node) < for (int i = 0; i < node->level; i++) cout son != NULL) cout level id key count_son != 0) for (int i = 0; i < node->count_son; i++) printTree(node->son[i]); > > void nodeKill(Node* node, int key) < >int main() < size_t number; int key; Node* root; setlocale(LC_ALL, "RUS"); root = new Node; root = createTree(root, 0, 0); cout > key; nodeKill(root, key); cout

Когда вызываете в цикле node->son[i] = new Node; , также прописывайте и указатель на parent — node->son[i]->parent = node; . Для root пропишите отдельно в main. Кстати, не понял, что такое у вас id , но вы создаете таким кодом массу узлов с одинаковым значением id

1 ответ 1

В принципе алгоритм такой:
если потомок 1

• в родительском узле указателю на удаляемый узел присваиваем указатель на потомка удаляемого узла
• в потомке указателю parent присваиваем адрес родительского узла удаляемого узла
• удаляем узел

• в родительском узле указателю на удаляемый узел присваиваем указатель на самого левого потомка удаляемого узла
• в самом левом потомке указателю parent присваиваем адрес родительского узла удаляемого узла
• добавляем указатели на сыновей из удаляемого узла к массиву указателей на сыновей самого левого потомка
• удаляем узел

Примерный код когда несколько потомков:

Node *DelNode = ; // каким-то образом вычисляем удаляемый узел Node *ParentNode = DelNode->parent; // запоминаем родителя Node *NewNode = DelNode->son[0]; // замещающим узлом будет самый левый потомок // находим в массиве указателей на потомков родительского узла указатель на текущий элемент. for( int i = 0; i < ParentNode->count_son; i++) if( ParentNode->son[i] == DelNode ) < ParentNode->son[i] = NewNode; // в массиве указателей на потомков родительского узла указателю на удаляемый элемент присваиваем значение самого левого потомка удаляемого узла break; > NewNode->parent = ParentNode; // указателю родителя дочернего узла присваиваем адрес родительского узла удаляемого элемента // теперь удаляемый элемент исключен из дерева и как-бы висит в воздухе вместе с потомками, кроме самого левого // нужно оставшихся потомков перепривязать к новому узлу Node *tmp = new Node[NewNode->count_son + DelNode->count_son - 1];// выделяем новую память под массив указателей на потомков в новом узле for(int j=0; jcount_son; j++) // копируем все указатели на потомков в новый массив tmp[j] = NewNode->son[j]; for(int j=1; jcount_son; j++) // копируем все указатели на потомков из удаляемого узла в новый массив нового узла tmp[NewNode->count_son + j - 1] = DelNode->son[j]; delete[] NewNode->son; // удаляем старый массив указателей на потомков NewNode->son = tmp; // запоминаем новый массив указателей NewNode->count_son = NewNode->count_son + DelNode->count_son - 1; // сохраняем новое количество потомков // Теперь удаляем старый узел delete[] DelNode->son; // сначала удаляем массив указателей на потомков delete DelNode; // а потом - сам узел 

Несколько замечаний по узлу дерева:

• key — неиспользуемое поле
• level — уровень иерархии нет особого смысла хранить, если этот параметр не используется в каких-то вычислениях
• Node* leftmost_child — бессмысленное поле, только усложняющее логику. Если речь о самом левом элементе в массиве, то это son[0]
• если разрешено условиями задачи, то для хранения указателей на потомков лучше использовать стандартные контейнеры vector<> или list<> . Тогда не нужно будет выделять/удалять память, количество элементов не надо хранить — всегда можно получить от контейнера и т.д.
  Как-то так:

struct Node < int //индекс Node* parent = nullptr; //указатель на родителя vectorson; //массив указателей на сыновей >; 

Источник

Удаление узла бинарного дерева

Есть бинарное дерево, надо удалить из него элемент.
Нашел вариант — удаляем элемент а на его место ставим либо самый правый элемент его левого поддерева либо самый левый его правого поддерева.
Вопрос: как это лучше всего организовать?
Логично, что надо у замещающего элемента дописать указатели на поддеревья а у его владельца заменить указатель на него на NULL, причем у владельца удаляемого элемента заменить указатель на замещающий элемент.
Если делать все в лоб, то нужны 2 указателя на поддеревья, указатели на родителей и указатели на сами элементы.
Есть ли некий правильный способ удаления без этого гемора? Возможно более оптимизированный. Просьба посмотреть мой код строка 164 — функция не линкуется, а вроде нормально написано.

1 ответ 1

В случае бинарного дерева поиска рекомендую посмотреть корректный алгоритм в Кормене («Алгоритмы. Построение и анализ» — страница 326), либо в более простом и наглядном варианте здесь.

В обоих случаях используется классическая структура данных для хранения BST , в которой элемент представлен кортежем (parent, left, right, data) .

В случае же обычного бинарного дерева нетривиальна только ситуация, когда у удаляемого элемента ссылки left и right — не null . В этой ситуации необходимо совершить обход по дереву в сторону left или right , найти первый возможный лист в дереве и заменить удаляемый элемент на данный лист.

Для оптимизации такой операции возможно хранить в каждом узле дерева дополнительное поле leaf , которое будет указывать на такой возможный лист, чтобы избежать прохода по ветке дерева в случае удаления элемента. Хотя, как мне кажется, интерес в такой оптимизации является сугубо теоретическим.

Источник