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

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

Войти
Регистрация
Восстановить пароль
 
CMson
2 / 2 / 2
Регистрация: 31.01.2013
Сообщений: 96
#1

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

01.06.2014, 21:28. Просмотров 808. Ответов 4
Метки нет (Все метки)

Добрый вечер!
Помогите, пожалуйста, написать деструктор для дерева.

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;
}
...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.06.2014, 21:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Деструктор для дерева (C++):

Почему создается виртуальный деструктор A, а в таблице виртуальных функций лежит деструктор B - C++
Почему я делаю виртуальным деструктор A, а в таблице виртуальных функций лежит деструктор B?

Деструктор для списков - C++
Ребята,как создать деструктор для списка в классе??? Подскажите-помагите пожалуйста!!Очень и срочно надо!!!!!

Деструктор для массива - C++
пишу шаблон класса: template <class T> class vector { T* array; public: int size;

Конструкторы и деструктор для списка на C++ - C++
Помогите, пожалуйста, не понимаю почему конструктор с параметрами и деструктор не работают. В случае конструктора с параметрами, он вроде...

Деструктор для встроенного типа - C++
Вечер добрый. Какой смысл у деструктора для встроенных типов? Такое вообще должно работать или "поведение не определено"? int main() { ...

Деструктор для массива матриц... - C++
Помогите написать деструктор для массива матриц.. Деструктор для матрицы вроде бы вот так пишется: { for (int z = 0; z < _rows;...

4
Max Dark
шКодер самоучка
1840 / 1640 / 596
Регистрация: 09.10.2013
Сообщений: 3,650
Записей в блоге: 6
Завершенные тесты: 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;
    }
}
0
CMson
2 / 2 / 2
Регистрация: 31.01.2013
Сообщений: 96
02.06.2014, 00:00  [ТС] #3
ругается, что rigth и left не известны в RBTree.
0
Max Dark
шКодер самоучка
1840 / 1640 / 596
Регистрация: 09.10.2013
Сообщений: 3,650
Записей в блоге: 6
Завершенные тесты: 2
02.06.2014, 00:39 #4
C++
1
2
node r = n->rigth;
        node l = n->left;
0
CMson
2 / 2 / 2
Регистрация: 31.01.2013
Сообщений: 96
02.06.2014, 14:01  [ТС] #5
А подскажите, для чего здесь нужен амперсанд?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.06.2014, 14:01
Привет! Вот еще темы с ответами:

конструктор и деструктор для cout - C++
Здарова! нужно решить задачу: есть код: int main() { cout <<"Hellow world"<<endl; } нужно без модифицирования...

Написать деструктор для данного класса - C++
Как лучше написать деструктор для класса: class Library{ private: struct books{ char* name; int year; ...

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

Виртуальный деструктор, для чего нужен? - C++
Я конечно понимаю, что Но объясните поподробнее и попонятнее для чего это нужно


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

Или воспользуйтесь поиском по форуму:
5
Yandex
Объявления
02.06.2014, 14:01
Ответ Создать тему
Опции темы

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