Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

Как удалять вершины бинарного дерева вместе с потомками?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2012, 16:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Удаление вершины бинарного дерева (C++):

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

Выделение памяти для поддерева(вершины) бинарного дерева поиска - C++
как выделить память под вершину бинарного дерева? Почему у меня неверно выделяется память? class tree { public: tree(); ...

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

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

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

Удаление из бинарного дерева - C++
Здравствуйте! Помогите с удалением узла из бинарного дерева. Номер узла вводится пользователем #include "stdafx.h" #include...

6
Marko
9 / 9 / 0
Регистрация: 05.07.2012
Сообщений: 38
11.07.2012, 16:23 #2
Зависит от того как ты представляешь дерево...
Если каждая вершина - класс, содержащий указатели на смежные к ней, то переопредели деструктор.
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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;
    }
}
0
pianist
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 56
12.07.2012, 18:36 #4
Рекурсивный при большом размере дерева не советую.
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.07.2012, 19:08 #5
pianist, можно развернуть в стек и цикл (по факту, реализовать обход в глубину).
1
pianist
0 / 0 / 0
Регистрация: 12.06.2012
Сообщений: 56
12.07.2012, 19:41 #6
так бы сразу и советовали.
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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();
    }
}
0
12.07.2012, 20:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2012, 20:34
Привет! Вот еще темы с ответами:

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

Удаление узла бинарного дерева - C++
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени помогите плиз. .cpp #include &lt;iostream&gt;...

Удаление элемента из бинарного дерева - C++
Ругается компилятор в Visual Studio при выполнении кода удаления элемента, а именно в том месте, где нужно удалить элемент с двумя...

Удаление бинарного дерева по слоям - C++
вот задачка такая встала и ни че в голову не приходит. как будет выглядеть функция чтоб удаляла бинарное дерево по слоям? плиззз...


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

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

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