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

Найти всех двойников в данном целочисленном бинарном дереве - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Генерация случайного числа каждую секунду http://www.cyberforum.ru/cpp-beginners/thread985695.html
Нужно каждую секунду генерировать случайное число. Ниже мой код, который выполняет задачу, но функция слип останавливает весь процесс и в дальнейшем может мешать (как например функция delay() в Ардуино). Есть ли еще какой-нибудь способ написать программу без ипользования Sleep() ? int x; for(int i=1;i<=5;i++){ x = rand() % 10; cout<< i <<" - "<< x <<endl; Sleep(1000); ...
C++ Формула подсчета количества итераций цикла for Доброго времени суток Помогите ответом/советом/уч. материалом Пусть, for( int i = 1; i <= 10; i++ ) ... имеем 10 итераций цикла for( int i = 11; i <= 17; i += 2 ) ... имеем 4 итерации цикла http://www.cyberforum.ru/cpp-beginners/thread985670.html
C++ Считать из файла определенную инфу в класс
Приветствую всех. Задача такая: Есть txt файл с инфой: 127 Киев-Львов 100 300 120 Москва-Киев 130 450 103 Будапешт-Москва 70 500 101 Донецк-Лисабон 35 430 Есть класс: class kassa {
C++ Получить из одной матрицы другую исходя из графической маски
Помогите разобраться с задачей! Сижу уже который день, никак не могу представить что тут к чему... Дана действительная матрица , i, j=1, ..., n. Получить действительную матрицу , i, j=1, ..., n, элемент bij которой равен сумме элементов данной матрицы, расположенных в области, определяемой индексами i,j так, как показано на рисунке ( область залита).
C++ Перегрузить функцию sub_array нахождения разности двух массивов и матриц http://www.cyberforum.ru/cpp-beginners/thread985622.html
Привет всем! Столкнулся со сложностями....Помогите сделать лабу! Задание: Перегрузить функцию sub_array нахождения разности двух массивов и матриц.
C++ Алгоритм удаления элемента из массива Помогите написать код:( Условие задачи таково: Заменить максимальный элемент из первых четырех его абсолютным значением, если они все отрицательны, иначе удалить только положительные элементы. подробнее

Показать сообщение отдельно
FIDES
2 / 2 / 0
Регистрация: 21.12.2014
Сообщений: 88
31.01.2016, 23:00     Найти всех двойников в данном целочисленном бинарном дереве
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
#include <iostream>
#include <iomanip>
#include <locale.h>
#include <fstream>
using namespace std;
 
struct tree
{
    int info;
    tree *left, *right;
};
 
//Прототипы
tree * MakeTree(int level);                                 //Создает бинарное дерево
tree * MakeTreeAuto(int level, ifstream & in);              //Создает бинарное дерево из файла
void PrintTree(tree * root, int level);                     //Выводит бинарное дерево на экран
void FindClone(tree * root);                                //Находит элементы-двойники
void SearchClone(tree * root, int level, int SearchLevel,   //Поиск двойников по уровням
                    int & TempPosition, int *LevelValues);
int MaxLevel(tree * root, int level);                       //Вычисляет максимальный уровень бинарного дерева
void SrchInArr(int * LevelValues, int TempPosition);        //Поиск двойников по массиву
 
void main()
{
    setlocale(LC_ALL,"Russian");
    tree * root;    //Инициализуем дерево
 
    cout << "1)Ввести новое дерево" << endl;
    cout << "2)Загрузить дерево A" << endl;
    cout << "3)Загрузить дерево B" << endl;
    cout << "4)Загрузить дерево C" << endl;
    int Select;
    cin >> Select;
 
    switch(Select)
    {
    case 1: 
        {
            root = MakeTree(0); //Создаем и заполняем бинарное дерево
            break;
        }
    case 2:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("1.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    case 3:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("2.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    case 4:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("3.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    default: return;    //Если выбор неверный - завершаем программу
    }
 
    cout << "Исходное дерево:" << endl;
    PrintTree(root, 0);
 
    cout << "Максимальный уровень " << MaxLevel(root, 0) << endl;
 
    FindClone(root);
 
    system("pause");
    return;
}
 
//Создает бинарное дерево(из файла)
tree * MakeTreeAuto(int level, ifstream & in)
{
    int c;      //Переменная для хранения текущего значения
    in >> c;    //Считываем из файла число(или переходим на следующее через пробел)
    if (c)      //Если это число не ноль то создаем ветвь
    {
        tree * p = new tree;
        p -> info = c;          //Присваиваем это значение ветви
 
        p -> left = MakeTreeAuto (level + 1, in);   //Создаем правое поддерево
 
        p -> right = MakeTreeAuto (level + 1, in);  //Создаем левое поддерево
 
        return p;
    }
    else
        return NULL;
}
 
//Создает бинарное дерево
tree * MakeTree(int level)
{
    char c;
    cout << setw(4*level) << "" << "Создать вершину? (y/n)" << endl;
    cin >> c;
 
    if (c == 'y')
    {
        tree * p = new tree;
        cout << setw(4*level) << "" << "Введите значение вершины" << endl;
        cin >> p -> info;
 
        cout << setw(4*level) << "" << "Левое поддерево вершины " << p -> info << endl;
        p -> left = MakeTree (level + 1);
 
        cout << setw(4*level) << "" << "Правое поддерево вершины " << p -> info << endl;
        p -> right = MakeTree (level + 1);
 
        return p;
    }
    else
        return NULL;
}
 
//Выводит бинарное дерево на экран
void PrintTree(tree * root, int level)
{
    if (root)
    {
        PrintTree(root -> left,level+1);
        cout <<setw(4*level)<< root -> info << endl;
        PrintTree(root -> right, level+1);
    }
    return;
}
 
//Вычисляет максимальный уровень бинарного дерева
int MaxLevel(tree * root, int level)
{
    if (root)
    {
        int left = MaxLevel(root -> left, level +1);    //Просматриваем левое поддерево
        int right = MaxLevel(root -> right, level +1);  //Просматриваем правое поддерево
        return max(left,right);                         //Возвращаем наибольшее значение уровня
    }
    else
        return level-1;
}
 
//Находит элементы-двойники
void FindClone(tree * root)
{
    if (root)
    {
        for (int i = 0; i <= MaxLevel(root,0); i++) //Проходим циклом от корня дерева до максимального уровня
        {
            int *LevelValues = new int[50]; //Значения текущего уровня(не более 50-ти)
            int TempPosition = 0;           //Текущая позиция в массиве значений
            SearchClone(root, 0, i, TempPosition, LevelValues);
            cout << "Элементы находящиеся на " << i << "-м уровне:" <<endl;
            for(int j = 0; j < TempPosition; j++)
                cout << LevelValues[j]<< " ";
            cout << endl;
            SrchInArr(LevelValues,TempPosition);
        }
    }
    return;
}
 
//Поиск клонов по уровням
void SearchClone(tree * root, int level, int SearchLevel , int & TempPosition, int *LevelValues)
{
    if (root)
    {
        if (level <= SearchLevel)   //Если этот уровень не больше, чем искомый
        {
            if (level == SearchLevel)
            {
                LevelValues[TempPosition] = root -> info;
                //cout << "Нашел элемент " << level << "-го уровня: " << root -> info << endl;  //!!ДЛЯ ОТЛАДКИ!!
                TempPosition ++;
            }
            else
            {
                SearchClone(root->left, level+1, SearchLevel, TempPosition, LevelValues);
                SearchClone(root->right, level+1, SearchLevel, TempPosition, LevelValues);
            }
        }
        else
            return;
    }
    return;
}
 
//Поиск двойников по массиву
void SrchInArr(int * LevelValues, int TempPosition)
{
    bool Check = false; //Наличие двойников
    int Temp;           //Текущий элемент массива
    for (int i = 0; i < TempPosition-1; i++)
    {
        Temp = LevelValues[i];
        for (int j = i+1; j < TempPosition; j++)
            if (Temp == LevelValues[j])
            {
                cout << "Найден двойник: " << Temp << endl;
                Check = true;
            }
    }
    if (!Check)
        cout << "Двойники не найдены" << endl;
 
    return;
}

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