2 / 1 / 2
Регистрация: 07.12.2016
Сообщений: 35
1

Определить, есть ли в данном бинарном дереве два одинаковых элемента

07.08.2017, 19:34. Показов 3776. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Взял задание на лето по курсу "Дискретная и вычислительная математика".
Одно из заданий такое (выдержки из методички):
2) Написать программу согласно своему заданию.
3) Граф отобразить, путь вывести. Если нет пути, вывести сообщение.
4) Ввод матрицы должен осуществляться из файла и через форму.
5) Представить для проверки результат выполнения работы в виде одного или нескольких файлов с исходным кодом на любом языке программирования.

Задание: Определить, если в данном бинарном дереве два одинаковых элемента.
И вот здесь я ничерта не понимаю чего от меня хотят: (Преподы в отпуске, спросить не у кого. Лето ведь.)

1. Какой смысл задавать дерево матрицей, если оно бинарное ? (Речь, вероятно, идёт о матрице смежности.)
2. Не могу сообразить формат удобочитаемого хранения в файле (я так понимаю - текстового) этого дерева. Ведь речь идёт, вероятно о несбалансилованном произвольном двоичном дереве, т.е. могущем содержать дубликаты и, в пределе, вырожденном в односвязный список.
3. По самому заданию: можно ли строить в ходе решения новое дерево, только уже сбалансированное поиска, с полем подсёта дубликатов ? Либо как-то по другому (без создания новых сущностей) оно решаемо ? Сортировкой на месте ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.08.2017, 19:34
Ответы с готовыми решениями:

Определить, есть ли в бинарном дереве хотя бы два одинаковых элемента
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента....

Как будут расположены два одинаковых элемента в бинарном дереве поиска?
допустим у меня есть такие числа : 50, 25, 16, 5 ,5 . Как будут расположены эти пятерки ?

Определить, есть ли в данном двумерном массиве два одинаковых элемента
1)Определить, есть ли в данном двумерном массиве два одинаковых элемента. 2)Написать программу,...

Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента
Не могу никак придумать сам алгоритм. Есть мысли: сравнивать последовательно каждый элемент с...

4
2717 / 1771 / 187
Регистрация: 05.06.2011
Сообщений: 5,129
08.08.2017, 17:40 2
1. Смысл учебной задачи учебен
2. Не можешь сообразить удобочитаемый — сообрази неудобочитаемый. В конце концов, среди требований удобочитаемости нет.
3. Как понимаю, у тебя два варианта: либо к концу лета прийти к преподу с вопросами — либо прийти к нему с работающей программой, к которой у него могут возникнуть замечания. Задавать здесь эти вопросы совершенно бесполезно за исключением сомнительного случая — если твой преподаватель зарегистрирован на форуме, он, возможно, ответит. Так что я б посоветовал второй
1
2 / 1 / 2
Регистрация: 07.12.2016
Сообщений: 35
08.08.2017, 20:46  [ТС] 3
Дык, из господ студентов, может кто делал такое задание ?
Интересует, собственно, не решение, а требования к нему.

На данный момент мне видится так:

1. Пишу упрощённый класс-аналог мультимножества STL.
2. Прохожу в любом порядке по заданному по условию дереву, одновременно добавляя его элементы в мультимножество.

Функцию вставки мультимножества пишу так, чтобы она возвращала количество вхождений ключа после вставки.
Как только функция вернёт больше 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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
#ifndef _avltree_
#define _avltree_
 
using namespace std;
 
enum Order {Preorder, Inorder, Postorder}; //порядок обхода дерева
 
template <class T> class Ttreenode //Структура узла дерева
{
public:
    T key; //хранимый объект
    unsigned int copies; //число копий объекта
    int height; //высота узла (отсчитывается от самого нижнего листа поддеревьев)
    Ttreenode * left; //лист имеет высоту 1
    Ttreenode * right;
    //конструктор
    Ttreenode(T k) {key = k; copies = 1; left = right = NULL; height = 1;};
};
 
template <class T> class Tavltree
{
    private:
        unsigned int keys;
        Ttreenode<T> * main_root;
        int height(Ttreenode<T> * ptr);
        int balance(Ttreenode<T> * ptr);
        void update_height(Ttreenode<T> * ptr);
        Ttreenode<T> * rotate_right(Ttreenode<T> * ptr);
        Ttreenode<T> * rotate_left(Ttreenode<T> * ptr);
        Ttreenode<T> * rebalance(Ttreenode<T> * ptr);
        Ttreenode<T> * add_node(Ttreenode<T> * root,const T &key);
        Ttreenode<T> * free_tree(Ttreenode<T> * root);
        Ttreenode<T> * find_min(Ttreenode<T> * ptr);
        Ttreenode<T> * remove_min(Ttreenode<T> * ptr);
        Ttreenode<T> * remove_node(Ttreenode<T> * root, const T &key); 
        void walk(Ttreenode<T> * ptr, Order order, int level, void (*callback)(Ttreenode<T> * , int));
        Ttreenode<T> * find_key(Ttreenode<T> * root, T key);
    public:
        Tavltree() {main_root = NULL; keys = 0;}; //конструктор по умолчанию
        unsigned int insert(const T &key);//добавляет объект в дерево, возвращает количество копий его после этого
        unsigned int find(const T &key);// ищет объект в дереве, возвращает количество копий
        unsigned int remove(const T&key);//удаляет объект, возвращает количество оставшихся копий
        ~Tavltree();
};
 
//Рекурсивный обход дерева
template <class T>
void Tavltree<T>::walk(Ttreenode<T> * ptr, Order order, int level, void (*callback)(Ttreenode<T> * , int))
{
    if (ptr==NULL) return;
    if ((order==Preorder)&&(callback!=NULL)) callback(ptr, level); 
    walk(ptr->left, order, level+1, callback);
    if ((order==Inorder)&&(callback!=NULL)) callback(ptr, level);
    walk(ptr->right, order, level+1, callback);
    if ((order==Postorder)&&(callback!=NULL)) callback(ptr, level); 
}
 
//Возвращает высоту поддерева для узла ptr
template <class T>
int Tavltree<T>::height(Ttreenode<T> * ptr)
{
    if (ptr==NULL) return 0; else return ptr->height;
}
//Возвращает разницу высот левого и правого поддеревьев узла ptr
template <class T>
int Tavltree<T>::balance(Ttreenode<T> * ptr)
{
    return height(ptr->right)-height(ptr->left);
}
//Обновляет поле height узла ptr на основе полей height его сыновей
template <class T>
void Tavltree<T>::update_height(Ttreenode<T> * ptr)
{
    ptr->height = max(height(ptr->left),height(ptr->right))+1;
}
// правый поворот вокруг узла ptr
template <class T>
Ttreenode<T> * Tavltree<T>::rotate_right(Ttreenode<T> * ptr)
{
    Ttreenode<T> * tmp = ptr->left;
    ptr->left = tmp->right;
    tmp->right = ptr;
    update_height(ptr);
    update_height(tmp);
    return tmp;
}
// левый поворот вокруг узла ptr
template <class T>
Ttreenode<T> * Tavltree<T>::rotate_left(Ttreenode<T> * ptr)
{
    Ttreenode<T> * tmp = ptr->right;
    ptr->right = tmp->left;
    tmp->left = ptr;
    update_height(ptr);
    update_height(tmp);
    return tmp;
}
// балансировка узла ptr
template <class T>
Ttreenode<T> * Tavltree<T>::rebalance(Ttreenode<T> * ptr)
{
    update_height(ptr);
    if(balance(ptr)==2)
        {
        if(balance(ptr->right) < 0) ptr->right = rotate_right(ptr->right);
        return rotate_left(ptr);
        }
    if(balance(ptr)==-2)
        {
        if(balance(ptr->left) > 0) ptr->left = rotate_left(ptr->left);
        return rotate_right(ptr);
        }
    return ptr;
}
//Рекурсивный поиск и добавление узла, с последующей балансировкой
template <class T>
Ttreenode<T> * Tavltree<T>::add_node(Ttreenode<T> * root,const T &key)
{
    if (root == NULL)
        {
        Ttreenode<T> * tmp = new Ttreenode<T>(key);
        if (tmp!=NULL)
            {
            keys = 1;
            return tmp;
            }
        else
            throw "Not enough memory ! (add_node)";
            exit(EXIT_FAILURE);
        }
    if (key < root->key)
        root->left = add_node(root->left, key);
    else if (key > root->key)
        root->right = add_node(root->right, key);
    else
        {//если узел существует, то меняем содержимое copies
        root->copies++;
        keys = root->copies;
        return root;
        }
    return rebalance(root);
};
 
//удаляет всё дерево
template <class T>
Ttreenode<T> * Tavltree<T>::free_tree(Ttreenode<T> * root)
{
    if (root!=NULL)
        {
        free_tree(root->left);
        free_tree(root->right);
        delete root;
        }
    return NULL;
}
// Поиск узла с ключом key в дереве root
// если нет узла, возвращает NULL иначе указ. на найденный узел
template <class T>
Ttreenode<T> * Tavltree<T>::find_key(Ttreenode<T> * root, T key)
{
    while (root!=NULL)
        {
        if (key == root->key) break;
        root = (key < root->key)?root->left:root->right;
        }
    return root;
}
// Поиск узла с минимальным ключом в поддереве ptr
// просто идём по левым ветвям
template <class T>
Ttreenode<T> * Tavltree<T>::find_min(Ttreenode<T> * ptr)
{
    while (ptr->left!=NULL) ptr=ptr->left;
    return ptr;
}
 
// удаление узла с минимальным ключом из поддерева ptr
template <class T>
Ttreenode<T> * Tavltree<T>::remove_min(Ttreenode<T> * ptr) 
{
    if (ptr->left == NULL) return ptr->right;
    ptr->left = remove_min(ptr->left);
    return rebalance(ptr);
}
 
// удаление узла с ключом key из дерева root
template <class T>
Ttreenode<T> * Tavltree<T>::remove_node(Ttreenode<T> * root, const T &key) 
{
    if (root==NULL) {keys = 0; return NULL;}
    if (key < root->key)
        root->left = remove_node(root->left, key);
    else if (key > root->key)
        root->right = remove_node(root->right, key);    
    else //нашли узел
        {
        //если несколько копий, то удаляем по одной
        keys = --(root->copies);
        if (keys) return root;
        //запоминаем потомков
        Ttreenode<T> * left_node = root->left;
        Ttreenode<T> * right_node = root->right;
        delete root; //удаляем узел
        //если нет потомков справа то выходим
        if( right_node==NULL ) return left_node;
        //а если есть, то ищем минимальный
        Ttreenode<T> * min = find_min(right_node);
        //и подвешиваем
        min->right = remove_min(right_node);
        min->left = left_node;
        return rebalance(min);
        }
    return rebalance(root);
}
 
template<class T>
Tavltree<T>::~Tavltree()
{
    main_root = free_tree(main_root);
}
 
template <class T>
unsigned int Tavltree<T>::insert(const T &key)
{
    main_root = add_node(main_root, key);
    return keys;
}
 
template <class T>
unsigned int Tavltree<T>::find(const T &key)
{
    Ttreenode<T> * ptr = main_root;
    unsigned int copies = 0;
    ptr = find_key(ptr, key);
    if (ptr != NULL) copies = ptr->copies;
    return copies;
}
 
//удаляет узел с ключом key возвращает сколько копий ключа осталось
template <class T>
unsigned int Tavltree<T>::remove(const T&key)
{
    main_root = remove_node(main_root, key);
    return keys;
}
 
#endif
main (тест):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include "avltree.hpp"
 
using namespace std;
 
void main()
{
    Tavltree<int> tree;
    cout << "insert (5) returned copies=" << tree.insert(5) << endl;
    cout << "insert (3) returned copies=" << tree.insert(3) << endl;
    cout << "insert (2) returned copies="<< tree.insert(2) << endl;
    cout << "insert (3) returned copies="<< tree.insert(3) << endl;
    cout << "search (2) returned copies="<< tree.find(2) << endl;
    cout << "search (3) returned copies="<< tree.find(3) << endl;
    cout << "delete (3) returned copies="<< tree.remove(3) << endl;
    cout << "search (3) returned copies="<< tree.find(3) << endl;
    system("pause");
}
0
2717 / 1771 / 187
Регистрация: 05.06.2011
Сообщений: 5,129
09.08.2017, 05:19 4
Ну, в принципе, почему б и нет. Осталось таки дописать ввод и отрисовку дерева. Ну и, если я правильно понял насчёт вывода пути, интересен не только сам факт дубля, но и пути к вершинам.
Цитата Сообщение от UnKaiF Посмотреть сообщение
3) Граф отобразить, путь вывести. Если нет пути, вывести сообщение
Надо доработать дерево для хранения ключа и информации, например.
0
2 / 1 / 2
Регистрация: 07.12.2016
Сообщений: 35
09.08.2017, 20:29  [ТС] 5
Кликните здесь для просмотра всего текста
Я понял идею. Это было бы интересно. Но, скорее всего, про путь - это для других вариантов заданий. Например, есть такие:
Найти путь максимальной длины между вершинами разной высоты.
0
09.08.2017, 20:29
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.08.2017, 20:29
Помогаю со студенческими работами здесь

Проверить, есть ли в непустом дереве хотя бы два одинаковых элемента
Описать логическую функцию проверяющую есть ли в непустом дереве хотя бы два одинаковых элемента

Описать логическую функцию, описывающую,есть ли в дереве Т хотя бы два одинаковых элемента
помогите пожалуйста решить задачу. описать логическую функцию, описывающую,есть ли в дереве Т хотя...

Написать функцию Double, которая проверяет, есть ли в дереве хотя бы два одинаковых элемента
Есть описание дерева type BT=longint; U=^BinTree; BIntree=record ...

Определить, есть ли в данном массиве два соседних отрицательных элемента?
Помогите решить: (просто, без всяких подпрограмм и т.д., нужно для блок схемы) Одномерный...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru