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

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

Войти
Регистрация
Восстановить пароль
 
МарияБелая
2 / 2 / 0
Регистрация: 13.03.2014
Сообщений: 79
#1

Удаление элемента из бинарного дерева - C++

13.07.2015, 21:06. Просмотров 826. Ответов 1
Метки нет (Все метки)

Ругается компилятор в Visual Studio при выполнении кода удаления элемента, а именно в том месте, где нужно удалить элемент с двумя дочерними элементами( в четвертом условии). Ошибка такая: "Unhandled exception at 0x0015483B in BinaryTree.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x001C2FFC)." Что исправить?
Код:
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
29
30
31
32
33
Tree* DeleteNode(Tree* node, int ch)
{
    /*Если удаляемый элемент находится в корне текущего поддерева и имеет два дочерних узла,
    то нужно заменить его минимальным элементом из правого поддерева
    и рекурсивно удалить минимальный элемент из правого поддерева.*/
 
    if (node == NULL)
        return node;
 
    if (ch < node->data)
    {
        node->left = DeleteNode(node->left, ch);
    }
    else if (ch > node->data)
    {
        node->right = DeleteNode(node->right, ch);
    }
    else if (node->left != NULL && node->right != NULL)
    {
        node->data = Minimum(node->right)->data;
        node->right = DeleteNode(node, node->right->data);
    }
    else if (node->left != NULL)
    {
        node = node->left;
    }
    else
    {
        node = node->right;
    }
 
    return node;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2015, 21:06     Удаление элемента из бинарного дерева
Посмотрите здесь:
C++ Удаление элемента из сбалансированого бинарного дерева
C++ Некорректное удаление элемента бинарного дерева поиска
Удаление из бинарного дерева C++
C++ Удаление узла бинарного дерева
C++ Удаление бинарного дерева по слоям
Удаление Узла бинарного дерева C++
Удаление Узла Бинарного Дерева. C++
Удаление вершины бинарного дерева C++
Освобождение памяти, удаление бинарного дерева C++
C++ Удаление элементов из бинарного дерева (не дерево поиска)
C++ Удаление узла бинарного дерева, проблема с функциями, адресацией
C++ Удаление узлов из бинарного дерева до даты, введенной с клавиатуры

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Геомеханик
545 / 352 / 263
Регистрация: 26.06.2015
Сообщений: 798
14.07.2015, 02:06     Удаление элемента из бинарного дерева #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cstdlib>
 
struct Tree {
    int   val;
    Tree* left;
    Tree* right;
};
 
Tree* InsertNode(Tree* node, int val);
void  PrintNode(std::ostream& _out, const Tree* node);
void  ClearNode(Tree* node);
 
 
//удаление
Tree* DeleteNode(Tree* node, int val){
    if(node == NULL)
        return node;
 
    if(val == node->val){
 
        Tree* tmp;
        if(node->right == NULL)
            tmp = node->left;
        else {
 
            Tree* ptr = node->right;
            if(ptr->left == NULL){
                ptr->left = node->left;
                tmp = ptr;
            } else {
 
                Tree* pmin = ptr->left;
                while(pmin->left != NULL){
                    ptr  = pmin;
                    pmin = ptr->left;
                }
                ptr->left   = pmin->right;
                pmin->left  = node->left;
                pmin->right = node->right;
                tmp = pmin;
            }
        }
 
        delete node;
        return tmp;
    } else if(val < node->val)
        node->left  = DeleteNode(node->left, val);
    else
        node->right = DeleteNode(node->right, val);
    return node;
}
 
 
int main(void){
    Tree* tree = NULL;
    for(int i = 0; i < 20; ++i)
        tree = InsertNode(tree, std::rand() % 10);
    
    PrintNode(std::cout, tree);
    std::cout << std::endl;
 
    tree = DeleteNode(tree, 5);
    tree = DeleteNode(tree, 2);
    tree = DeleteNode(tree, 9);
    
    PrintNode(std::cout, tree);
    ClearNode(tree);
    return 0;
}
 
 
//вставка
Tree* InsertNode(Tree* node, int val){
    if(node == NULL){
        node = new (std::nothrow) Tree();
        if(node != NULL){
            node->val  = val;
            node->left = node->right = NULL;
        }
        return node;
    }
 
    if(val < node->val)
        node->left  = InsertNode(node->left, val);
    else
        node->right = InsertNode(node->right, val);
    return node;
}
 
//печать
void PrintNode(std::ostream& _out, const Tree* node){
    if(node != NULL){
        if(node->left != NULL)
            PrintNode(_out, node->left);
 
        _out << node->val << ' ';
 
        if(node->right != NULL)
            PrintNode(_out, node->right);
    }
}
 
//удаление всего
void ClearNode(Tree* node){
    if(node != NULL){
        if(node->left != NULL)
            ClearNode(node->left);
        if(node->right != NULL)
            ClearNode(node->right);
        delete node;
    }
}
Проверка работы кода
Yandex
Объявления
14.07.2015, 02:06     Удаление элемента из бинарного дерева
Ответ Создать тему
Опции темы

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