Skip to content

Commit 6e9779a

Browse files
rudi8848rudi8848
committed
tree check
1 parent 75fa3ad commit 6e9779a

3 files changed

Lines changed: 185 additions & 0 deletions

File tree

‎4/tree_check.cpp‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
#include <iostream>
2+
#include <vector>
3+
4+
struct Node
5+
{
6+
int val;
7+
int left;
8+
int right;
9+
};
10+
11+
class Tree
12+
{
13+
public:
14+
Tree(int n) {
15+
_tree.resize(n);
16+
int val, left, right;
17+
for (int i = 0; i < n; ++i) {
18+
std::cin >> val >> left >> right;
19+
_tree[i].val = val;
20+
_tree[i].left = left;
21+
_tree[i].right = right;
22+
}
23+
}
24+
~Tree() {}
25+
void InOrder(int v) {
26+
if (v == -1)
27+
return;
28+
InOrder(_tree[v].left);
29+
_output.push_back(_tree[v].val);
30+
InOrder(_tree[v].right);
31+
}
32+
bool check() {
33+
InOrder(0);
34+
int prev = _output[0];
35+
for (int i = 1; i < _output.size(); ++i) {
36+
int current = _output[i];
37+
if (! (current > prev))
38+
return false;
39+
prev = current;
40+
}
41+
42+
return true;
43+
}
44+
private:
45+
std::vector<Node> _tree;
46+
std::vector<int> _output;
47+
};
48+
49+
int main(void) {
50+
int n;
51+
std::string res;
52+
std::cin >> n;
53+
if (!n)
54+
{
55+
std::cout <<"CORRECT"<< std::endl;
56+
return 0;
57+
}
58+
Tree tree(n);
59+
res = tree.check() ? "CORRECT" : "INCORRECT";
60+
std::cout << res << std::endl;
61+
return 0;
62+
}

‎4/tree_check1.cpp‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
#include <iostream>
2+
#include <vector>
3+
4+
struct Node
5+
{
6+
long long val;
7+
int left;
8+
int right;
9+
};
10+
11+
class Tree
12+
{
13+
public:
14+
Tree(int n) {
15+
_tree.resize(n);
16+
int left, right;
17+
long long val;
18+
for (int i = 0; i < n; ++i) {
19+
std::cin >> val >> left >> right;
20+
_tree[i].val = val;
21+
_tree[i].left = left;
22+
_tree[i].right = right;
23+
}
24+
}
25+
~Tree() {}
26+
27+
28+
void check() {
29+
long long full_lo, full_hi;
30+
if (get_and_check_tree_range(0, full_lo, full_hi))
31+
std::cout << "CORRECT" << std::endl;
32+
else
33+
std::cout << "INCORRECT" << std::endl;
34+
}
35+
private:
36+
bool get_and_check_tree_range(int v, long long &lo, long long &hi) {
37+
38+
lo = hi = _tree[v].val;
39+
if (_tree[v].left != -1)
40+
{
41+
long long left_lo, left_hi;
42+
if (!get_and_check_tree_range(_tree[v].left, left_lo, left_hi))
43+
return false;
44+
if (! (left_lo <= left_hi))
45+
return false;
46+
if (left_hi >= _tree[v].val)
47+
return false;
48+
lo = left_lo;
49+
}
50+
if (_tree[v].right != -1)
51+
{
52+
long long right_lo, right_hi;
53+
if (!get_and_check_tree_range(_tree[v].right, right_lo, right_hi))
54+
return false;
55+
if ( !(right_lo <= right_hi))
56+
return false;
57+
if (right_lo < _tree[v].val)
58+
return false;
59+
hi = right_hi;
60+
}
61+
return true;
62+
}
63+
64+
std::vector<Node> _tree;
65+
};
66+
67+
int main(void) {
68+
int n;
69+
std::cin >> n;
70+
if (!n)
71+
{
72+
std::cout <<"CORRECT"<< std::endl;
73+
return 0;
74+
}
75+
Tree tree(n);
76+
tree.check();
77+
return 0;
78+
}

‎README.md‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,2 +1,47 @@
11
# data_structures
22
Задачи курса Stepic "Алгоритмы: теория и практика. Структуры данных"
3+
1. Базовые структуры данных.
4+
- Скобки в коде
5+
Проверить, правильно ли расставлены скобки в данном коде.
6+
- Высота дерева
7+
Вычислить высоту данного дерева.
8+
- Обработка сетевых пакетов
9+
Реализовать обработчик сетевых пакетов.
10+
- Стек с поддержкой максимума
11+
Реализовать стек с поддержкой операций push, pop и max
12+
- Максимум в скользящем окне
13+
Найти максимум в каждом окне размера m данного массива чисел
14+
A[1 . . . n].
15+
2. Очереди с приоритетом. Системы непересекающихся множеств.
16+
- Построение кучи
17+
Переставить элементы заданного массива чисел так, чтобы он удовлетворял свойству мин-кучи.
18+
- Параллельная обработка
19+
По данным n процессорам и m задач определите, для каждой из задач,
20+
каким процессором она будет обработана.
21+
- Объединение таблиц
22+
Ваша цель в данной задаче — реализовать симуляцию объединения
23+
таблиц в базе данных.
24+
- Автоматический анализ программ
25+
Система равенств и неравенств
26+
Проверить, можно ли присвоить переменным целые значения, чтобы
27+
выполнить заданные равенства вида xi = xj и неравенства вида xp != xq.
28+
3. Хеш-таблицы.
29+
- Телефонная книга
30+
Реализовать структуру данных, эффективно обрабатывающую запросы вида add number name, del number и find number.
31+
- Хеширование цепочками
32+
Ваша цель в данной задаче — реализовать схему хеширования цепочками, используя таблицу с m ячейками и полиномиальной хеш-функцией.
33+
- Поиск образца в тексте
34+
Найти все вхождения строки Pattern в строку Text.Реализуйте алгоритм Карпа–Рабина.
35+
4. Деревья поиска.
36+
- Обход двоичного дерева
37+
Построить in-order, pre-order и post-order обходы данного двоичного дерева.
38+
- Проверка свойства дерева поиска
39+
Проверить, является ли данное двоичное дерево деревом поиска.
40+
- Проверка более общего свойства дерева поиска
41+
- Множество с запросами суммы на отрезке
42+
Реализуйте структуру данных для хранения множества целых чисел,
43+
поддерживающую запросы добавления, удаления, поиска, а также
44+
суммы на отрезке.
45+
- Rope
46+
Ваша цель в данной задаче — реализовать структуру данных Rope.
47+
Данная структура данных хранит строку и позволяет эффективно вырезать кусок строки и переставить его в другое место.

0 commit comments

Comments
 (0)