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

Деструктор для дерева - C++

Восстановить пароль Регистрация
 
CMson
2 / 2 / 2
Регистрация: 31.01.2013
Сообщений: 96
01.06.2014, 21:28     Деструктор для дерева #1
Добрый вечер!
Помогите, пожалуйста, написать деструктор для дерева.

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
enum color { RED, BLACK };
// Звено дерева
typedef struct rbtree_node
{
    // Звено окрашено в черный или красный цвет
    enum color color;
    // Поле для ключа
    int key;
    // Поле для данных
    int value;
    // Указатели на соседей и предка
    rbtree_node *left, *right, *parent;
}*node;
 
// Класс красно-черное дерево
class RBTree
{
public:
    RBTree();
    ~RBTree();
    // Вставка по типу размещения
    void insert_case1(node n);
    void insert_case2(node n);
    void insert_case3(node n);
    void insert_case4(node n);
    void insert_case5(node n);
 
    // Удаление звена
    void delete_case1(node n);
    void delete_case2(node n);
    void delete_case3(node n);
    void delete_case4(node n);
    void delete_case5(node n);
    void delete_case6(node n);
 
    void Destroy(node n);
 
    void print_tree();
 
    // Вставка нового звена в дерево
    void rbtree_insert(int key, int value);
    // Удаление звена из дерева
    void rbtree_delete(int key);
 
    int rbtree_lookup(int root);
 
    int compare(int leftp, int rightp);
 
    // Новое звено
    node new_node(int key, int value, color, node, node);
    node lookup_node(int root);
 
 
private:
    // Получить родителя текушего родителя
    node grandparent(node n);
    // Получить звено - брат: элемент находящийся на том же уровне что и текущее звено
    node sibling(node n);
    // Получить родителя "брата"
    node uncle(node n);
    // Получаем цвет звена
    color node_color(node n);
    // Получаем максимум
    node maximum_node(node root);
    // Поворот влево
    void rotate_left(node n);
    // Поворот вправо
    void rotate_right(node n);
    // Обмен местами
    void replace_node(node oldn, node newn);
 
    // Проверка свойств красно - черного дерева
    void verify_properties(node root);
    void verify_property_1(node root);
    void verify_property_2(node root);
    void verify_property_4(node root);
    void verify_property_5(node root);
    void verify_property_5_helper(node n, int, int*);
    node root;
};
 
// Получаем родителя у текущего родителя
node RBTree::grandparent(node n)
{
    assert(n != NULL);//если есть звено
    assert(n->parent != NULL);//у звена есть родитель
    assert(n->parent->parent != NULL);//у звена родителя есть родитель, то возвращаем это значение
    return n->parent->parent;
}
 
// Получить звено - брат: элемент находящийся на том же уровне что и текущее звено
node RBTree::sibling(node n)
{
    assert(n != NULL);
    assert(n->parent != NULL);
    if (n == n->parent->left)//если звено слева, возвращаем то, которое справа и наоборот
        return n->parent->right;
    else
        return n->parent->left;
}
 
// Получить родителя "брата"
node RBTree::uncle(node n)
{
    assert(n != NULL);
    assert(n->parent != NULL);//то же самое только для родителя
    assert(n->parent->parent != NULL);
    return sibling(n->parent);
}
// Получаем цвет звена
color RBTree::node_color(node n)
{
    return n == NULL ? BLACK : n->color;
}
// Максимальный элемент
node RBTree::maximum_node(node n)
{
    assert(n != NULL);
    while (n->right != NULL)
    {
        n = n->right;
    }
    return n;
}
 
...
 
// Конструктор
RBTree::RBTree()
{
    root = NULL;
}
 
//деструктор
RBTree::~RBTree() 
{
    if (root != NULL)
    {
        Destroy(root);
    }
}
 
void RBTree::Destroy(node n)  // Удаление дерева
{
    if (this != NULL)
    {
        node r = this->rigth;
        node l = this->left;
        Destroy(r);
        Destroy(l);
        delete this;
    }
}
 
node RBTree::new_node(int k, int v, color n_color, node left, node right)
{
    node result = new rbtree_node;
    result->key = k;
    result->value = v;
    result->color = n_color;
    result->left = left;
    result->right = right;
    if (left != NULL)
        left->parent = result;
    if (right != NULL)
        right->parent = result;
    result->parent = NULL;
    return result;
}
...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.06.2014, 21:28     Деструктор для дерева
Посмотрите здесь:

C++ Деструктор для массива матриц...
Деструктор для массива C++
Деструктор для списков C++
конструктор и деструктор для cout C++
C++ Деструктор для встроенного типа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Max Dark
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
01.06.2014, 23:53     Деструктор для дерева #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
void RBTree::Destroy(node &n)  // Удаление дерева
{
    if (n != NULL)
    {
        node r = this->rigth;
        node l = this->left;
        Destroy(r);
        Destroy(l);
        delete n;
        n = NULL;
    }
}
CMson
2 / 2 / 2
Регистрация: 31.01.2013
Сообщений: 96
02.06.2014, 00:00  [ТС]     Деструктор для дерева #3
ругается, что rigth и left не известны в RBTree.
Max Dark
В поиске работы
 Аватар для Max Dark
1546 / 1399 / 501
Регистрация: 09.10.2013
Сообщений: 3,185
Записей в блоге: 8
Завершенные тесты: 2
02.06.2014, 00:39     Деструктор для дерева #4
C++
1
2
node r = n->rigth;
        node l = n->left;
CMson
2 / 2 / 2
Регистрация: 31.01.2013
Сообщений: 96
02.06.2014, 14:01  [ТС]     Деструктор для дерева #5
А подскажите, для чего здесь нужен амперсанд?
Yandex
Объявления
02.06.2014, 14:01     Деструктор для дерева
Ответ Создать тему
Опции темы

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