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

дерево поиска Т1 для дерева Т - C++

Восстановить пароль Регистрация
 
nesm
0 / 0 / 0
Регистрация: 18.04.2010
Сообщений: 4
18.12.2010, 16:55     дерево поиска Т1 для дерева Т #1
Здравствуйте!
Пишу курсовой с вот таким задание:

1. Создать идеально сбалансированное дерево Т, распечатать его (в виде дерева),
2 .определить максимальную глубину дерева,
3.определить есть ли в дереве хотя бы 2 одинаковых элемента.
4. построить и напечатать по уровням дерево поиска Т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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include "exception.h"
#include "node.h"
 
// конструктор
Node::Node(double e)
{
    element = e;
    left = NULL;
    right = NULL;
}
 
// конструктор копирования
Node::Node(Node& other)
{
    element = other.element;
    left = NULL;
    right = NULL;
    if(other.left) left = new Node(*other.left);
    if(other.right) right = new Node(*other.right);
}
 
// деструктор
Node::~Node()
{
    // рекурсивное удаление всех узлов левого поддерева
    // благодаря автоматическому вызову их деструкторов
    delete left;
 
    // рекурсивное удаление всех узлов правого поддерева
    // благодаря автоматическому вызову их деструкторов
    delete right;
}
 
// оператор присваивания
Node& Node::operator=(Node& other)
{
    element = other.element;
    delete left;
    delete right;
    left = NULL;
    right = NULL;
    if(other.left) left = new Node(*other.left);
    if(other.right) right = new Node(*other.right);
    return *this;
}
 
// оператор сравнения
bool Node::operator==(Node& other)
{
    if(element != other.element) return false;
 
    if(left && !other.left) return false;
    if(!left && other.left) return false;
 
    if(right && !other.right) return false;
    if(!right && other.right) return false;
 
    if(left && other.left && !(*left == *other.left)) return false;
    if(right && other.right && !(*right == *other.right)) return false;
 
    return true;
}
 
// размер поддерева (число элементов)
int Node::size()
{
    int size = 1;
 
    // рекурсивный подсчет размеров поддеревьев
    if(left) size += left->size();
    if(right) size += right->size();
 
    return size;
}
 
// балансировка для поддержания дерева
// в идеально сбалансированном состоянии
void Node::balance()
{
    int left_size = 0;
    if(left) left_size = left->size();
 
    int right_size = 0;
    if(right) right_size = right->size();
 
    // если левое поддерево больше, чем на 1 от правого
    if(left_size - right_size > 1)
    {
        // если правого узла нет, то создание правого узла с текущим элементом
        if(right == NULL) right = new Node(element);
        // иначе добавление текущего элемента в правый узел
        else *right += element;
 
        // поиск указателя на максимальный элемент в левом поддереве
        Node** p = &left;
        while((*p)->right) p = &(*p)->right;
 
        // этот максимальный элемент становится текущим
        element = (*p)->element;
 
        // удаление узла с максимальным элементом
        // с удочерением его левого поддерева
        Node* removed = (*p);
        (*p) = (*p)->left;
        removed->left = NULL;
        delete removed;
    }
    // если правое поддерево больше, чем на 1 от левого
    else if(right_size - left_size > 1)
    {
        // если левого узла нет, то создание левого узла с текущим элементом
        if(left == NULL) left = new Node(element);
        // иначе добавление текущего элемента в левый узел
        else *left += element;
 
        // поиск указателя на минимальный элемент в правом поддереве
        Node** p = &right;
        while((*p)->left) p = &(*p)->left;
 
        // этот минимальный элемент становится текущим
        element = (*p)->element;
 
        // удаление узла с минимальным элементом
        // с удочерением его правого поддерева
        Node* removed = (*p);
        (*p) = (*p)->right;
        removed->right = NULL;
        delete removed;
    }
 
    // рекурсивная балансировка поддеревьев
    if(left) left->balance();
    if(right) right->balance();
}
 
// оператор добавления элемента
void Node::operator+=(double e)
{
    // если добавляемый элемент меньше текущего, то добавление влево
    if(e < element)
    {
        // если левого узла нет, то создание левого узла
        if(left == NULL) left = new Node(e);
        // иначе добавление элемента в левый узел
        else *left += e;
    }
    // иначе добавление вправо
    else
    {
        // если правого узла нет, то создание правого узла
        if(right == NULL) right = new Node(e);
        // иначе добавление элемента в правый узел
        else *right += e;
    }
}
 
// печать узла
void Node::print(int depth)
{
    // печать левого поддерева (если есть)
    if(left) left->print(depth + 1);
 
    // печать пробелов до нужной глубины текущего узла
    for(int i = 0; i < depth; i++) cout << "  ";
 
    // печать элемента
    cout << element << endl;
 
    // печать правого поддерева (если есть)
    if(right) right->print(depth + 1);
}
 
// определение максимальной глубины
int Node::max_depth()
{
    // своя глубина
    int depth = 1;
 
    // глубина левого поддерева
    int left_depth = 1;
    if(left) left_depth = 1 + left->max_depth();
 
    // глубина правого поддерева
    int right_depth = 1;
    if(right) right_depth = 1 + right->max_depth();
 
    // возвращение максимума из трех глубин
    if(left_depth > depth) depth = left_depth;
    if(right_depth > depth) depth = right_depth;
    return depth;
}
 
// определение есть ли в поддереве хотя бы 2 одинаковых элемента
bool Node::contains_same_elements()
{
    // определение совпадает ли текущий элемент с левым/правым
    if(left && left->element == element) return true;
    if(right && right->element == element) return true;
 
    // рекурсивное определение по дочерним узлам
    if(left && left->contains_same_elements()) return true;
    if(right && right->contains_same_elements()) return true;
 
    // ничего не найдено
    return false;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.12.2010, 16:55     дерево поиска Т1 для дерева Т
Посмотрите здесь:

Бинарное Дерево(обход дерева) C++
C++ Итератор для бинарного дерева поиска.
из сбалансированного дерева в дерево поиска C++
C++ Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
C++ Преобразование идельносбалансированного дерева в дерево поиска
Бинарное дерево, расчёт суммы элементов дерева C++
C++ Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
C++ Удаление элементов из бинарного дерева (не дерево поиска)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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