Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
0 / 0 / 0
Регистрация: 09.07.2012
Сообщений: 11
1

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

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

Как удалять вершины бинарного дерева вместе с потомками?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.07.2012, 16:16
Ответы с готовыми решениями:

не листовые вершины бинарного дерева, где находятся?
этими вершинами не являются ли сами листья дерева?

Выделение памяти для поддерева(вершины) бинарного дерева поиска
как выделить память под вершину бинарного дерева? Почему у меня неверно выделяется память? class...

Пронумеровать вершины бинарного дерева в соответствии с порядком концевого обхода
Здравствуйте!!!! Помогите пожалуйста решить задачу. Построить бинарное дерево поиска для заданного...

Для каждой вершины бинарного дерева, поменять местами дочерние элементы
Дано бинарное дерево.(заполняется с клавиатуры). Для каждой вершины, имеющей дочернюю, поменять...

6
9 / 9 / 0
Регистрация: 05.07.2012
Сообщений: 38
11.07.2012, 16:23 2
Зависит от того как ты представляешь дерево...
Если каждая вершина - класс, содержащий указатели на смежные к ней, то переопредели деструктор.
0
Эксперт С++
5036 / 3096 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
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;
    }
}
0
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 56
12.07.2012, 18:36 4
Рекурсивный при большом размере дерева не советую.
0
Эксперт С++
5036 / 3096 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
12.07.2012, 19:08 5
pianist, можно развернуть в стек и цикл (по факту, реализовать обход в глубину).
1
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 56
12.07.2012, 19:41 6
так бы сразу и советовали.
0
Эксперт С++
5036 / 3096 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
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();
    }
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.07.2012, 20:34

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Удаление вершины дерева поиска
Здравствуйте. Не получается написать удаление вершины из дерева поиска, что бы после удаления,...

Удаление из бинарного дерева
Здравствуйте! Помогите с удалением узла из бинарного дерева. Номер узла вводится пользователем ...

Удаление узла из бинарного дерева
всем доброго времени суток. помогите пожалуйста с удалением элемента из дерево, а именно с...

Удаление Узла бинарного дерева
Добрый вечер. Имеем Бинарное дерево поиска. При удалении некоторого узла . возникают три...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.