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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Создать конструктор http://www.cyberforum.ru/cpp-beginners/thread213988.html
Используя следующий фрагмент, создайте е конструктор саг(). Он должeн передавать необходимые аргументы объектам класса vehicle. Кроме этого конструктор саг() должен при создании объекта инициализировать переменную passengers. #include <iostream> using namespace std; // Базовый класс автомобилей для разных типов class vehicle { int num_wheels; int range; public: vehicle (int w, int r)
C++ Посчитайте количество натуральных чисел, не превосходящих 60 1)Даны два натуральных числа A и B. Известно, что их произведение, записанное в семеричной системе счисления равно 143 в 7 системе счисления. Найдите сумму чисел A и B, если известно, что одно из чисел является минимально возможным трехразрядным числом, записанным в четверичной системе счисления. В ответе запишите сумму чисел А и В в десятичной системе счисления. 2)Посчитайте количество... http://www.cyberforum.ru/cpp-beginners/thread213981.html
Перевести коды из Pas в C++ C++
{осуществить циклический сдвиг элементов массива, на k позиций вправо } program li; uses crt; var a:array of integer; i,r,n,k,j:integer; begin writeln('введите размер массива ') ; readln(n); write('введите величину сдвига ') ;
C++ char* to char
Подскажите, как перевести char* в char!
C++ Длина массива в списке http://www.cyberforum.ru/cpp-beginners/thread213971.html
ув. программисты,имеется такая инициализация: struct TRecord {int x,y;int elem; char c; bool step;} all; Как присвоить всем елементам массива elem 0.просто если тут расписывать получится гигантская запись,а если не тут то получится еще хуже.можно как то разом всем числам одно значение присвоить? З.ы. переименуйте пожалуйста модераторы в инициализацию массива в списке
C++ Работа с массивами структур Поля структуры: код студента, фамилия, предмет, оценка. Операция: найти средний балл студента с введенной фамилией. знаю, что писал уже, но я немного не разобрался... написал вот такую вот фигню =) #include <iostream> using namespace std; подробнее

Показать сообщение отдельно
nesm
0 / 0 / 0
Регистрация: 18.04.2010
Сообщений: 4
18.12.2010, 16:55     дерево поиска Т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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 12:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru