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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Jack33
0 / 0 / 0
Регистрация: 09.07.2012
Сообщений: 11
#1

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

11.07.2012, 16:16. Просмотров 877. Ответов 6
Метки нет (Все метки)

Как удалять вершины бинарного дерева вместе с потомками?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Marko
9 / 9 / 0
Регистрация: 05.07.2012
Сообщений: 38
11.07.2012, 16:23     Удаление вершины бинарного дерева #2
Зависит от того как ты представляешь дерево...
Если каждая вершина - класс, содержащий указатели на смежные к ней, то переопредели деструктор.
silent_1991
Эксперт C++
4949 / 3025 / 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++
4949 / 3025 / 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++ Выделение памяти для поддерева(вершины) бинарного дерева поиска
Удаление из бинарного дерева C++
Для каждой вершины бинарного дерева, поменять местами дочерние элементы C++

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4949 / 3025 / 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     Удаление вершины бинарного дерева
Ответ Создать тему
Опции темы

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