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

Question

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

Метод удаления: если у узла нет потомков, то он удаляется. Если у узла есть хотя бы 1 потомок, то узел заменяется его крайним левым дочерним узлом.

#include <iostream>

using namespace std;

struct Node 
{
    int key = NULL; //ключ
    int id = 0; //индекс
    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 << "Текущая позиция: " << node->level << "-" << node->id << "\n" << "Введите степень узла + его ключ: ";
    cin >> 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 << "| ";
        if (node->son != NULL) cout << "[+]";
        cout << "(" << node->level << "-" << node->id << ") = "<< node->key << endl;
        if (node->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 << "\n-----Получившееся дерево-----\n";
    printTree(root);
    cout << "Введите ключ узла, который хотите удалить: ";
    cin >> key;
    nodeKill(root, key);
    cout << "\n-----Дерево с удалённым узлом-----\n";
    printTree(root);
    system("pause");
    return 0;
}

Answer 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; j<NewNode->count_son; j++) // копируем все указатели на потомков в новый массив
   tmp[j] = NewNode->son[j];

for(int j=1; j<DelNode->count_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 id = 0; //индекс
    Node* parent = nullptr; //указатель на родителя
    vector<Node*> son;  //массив указателей на сыновей
};

БЛОГ НА HUSL

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

Ответы (1 шт):