Форум программистов, компьютерный форум CyberForum.ru

Удаление вершины бинарного дерева - C++

Восстановить пароль Регистрация
 
Jack33
0 / 0 / 0
Регистрация: 09.07.2012
Сообщений: 11
11.07.2012, 16:16     Удаление вершины бинарного дерева #1
Как удалять вершины бинарного дерева вместе с потомками?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Marko
9 / 9 / 0
Регистрация: 05.07.2012
Сообщений: 38
11.07.2012, 16:23     Удаление вершины бинарного дерева #2
Зависит от того как ты представляешь дерево...
Если каждая вершина - класс, содержащий указатели на смежные к ней, то переопредели деструктор.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.07.2012, 18:18     Удаление вершины бинарного дерева #3
Jack33, с помощью рекурсивного обхода. Фактически метод delete_node будет выглядеть примерно так:
C++
1
2
3
4
5
6
7
8
9
void BinaryTree::delete_node(BinaryTreeNode *node)
{
    if (node != 0)
    {
        delete_node(node->left_child);
        delete_node(node->right_child);
        delete node;
    }
}
pianist
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 56
12.07.2012, 18:36     Удаление вершины бинарного дерева #4
Рекурсивный при большом размере дерева не советую.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.07.2012, 19:08     Удаление вершины бинарного дерева #5
pianist, можно развернуть в стек и цикл (по факту, реализовать обход в глубину).
pianist
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 56
12.07.2012, 19:41     Удаление вершины бинарного дерева #6
так бы сразу и советовали.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2012, 20:34     Удаление вершины бинарного дерева
Еще ссылки по теме:

не листовые вершины бинарного дерева, где находятся? C++
C++ Удаление элементов из бинарного дерева (не дерево поиска)
C++ Удаление элемента из бинарного дерева

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.07.2012, 20:34     Удаление вершины бинарного дерева #7
Маленько погорячился с обычным обходом в глубину. Во-первых, нужен обход в ширину, а во-вторых, обратный (т.е. с нижних уровней к верхним), чтобы всё корректно удалилось. По крайней мере, я пришёл к такому выводу, возможно, есть способ проще. Вот такой код у меня вышел, на основе очереди и стека:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void BinaryTree::delete_tree()
    std::queue<BinaryTreeNode *> nodes_queue;
    std::stack<BinaryTreeNode *> nodes_stack;
    TreeNode *node = m_root;
    
    nodes_queue.push(node);
    
    while (!nodes_queue.empty())
    {
        node = nodes_queue.front();
        
        if (node->left != 0)
            nodes_queue.push(node->left);
        
        if (node->right != 0)
            nodes_queue.push(node->right);
        
        nodes_queue.pop();
        nodes_stack.push(node);
    }
    
    while (!nodes_stack.empty())
    {
        delete nodes_stack.top();
        
        nodes_stack.pop();
    }
}
Yandex
Объявления
12.07.2012, 20:34     Удаление вершины бинарного дерева
Ответ Создать тему
Опции темы

Текущее время: 16:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru