Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct Node
- {
- int key; // ключ узла
- Node* left; // указатель на левого потомка
- Node* right; // указатель на правого потомка
- Node* parent; // указатель на предка
- };
- /*
- Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения,
- будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём
- номер,
- нарушающий убывающую последовательность,
- а для каждого такого номера будем искать вершину без правого потомка,
- хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней
- элемент
- с таким номером в качестве правого сына.
- Когда мы, желая найти такую вершину, встречаем какую-нибудь другую,
- уже имеющую правого сына, проходим по ветке вправо. Мы имеем на это право, так как если такая
- вершина стоит,
- то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону
- смысла не имеет.
- Вершину с максимальным ключом, с которой будем начинать поиск, будем запоминать. Она будет
- обновляться каждый раз,
- когда появится новый максимум.
- */
- Node* find_parent(Node* curr, int idx, Node* tree)
- {
- if (curr->key <= tree[idx].key && curr->right == NULL)
- {
- tree[idx].parent = curr;
- curr->right = &tree[idx];
- curr = &tree[idx];
- return curr;
- }
- if (curr->right != NULL)
- {
- find_parent(curr->right, idx, tree);
- }
- return curr;
- }
- void f(int k, Node* tree, int n, Node* curr)
- {
- while (k < n - 1 && tree[k + 1].key <= tree[k].key) //<= ?
- {
- tree[k].left = &tree[k + 1];
- tree[k + 1].parent = &tree[k];
- k++;
- }
- curr = find_parent(curr, k + 1, tree); //Обновляем вершину с макс ключом
- if (k + 2 <= n - 1) //Если посмотрели еще не все вершины то запускаем
- f(k + 2, tree, n, curr);
- }
- void preorderTraversal(Node* x)
- {
- if (x != NULL)
- {
- cout << x->key << endl;
- preorderTraversal(x->left);
- preorderTraversal(x->right);
- }
- return;
- }
- int main()
- {
- int n;
- cin >> n;
- Node tree[n];
- for (int i = 0; i < n; ++i)
- {
- tree[i].right = NULL;
- tree[i].left = NULL;
- tree[i].parent = NULL;
- cin >> tree[i].key; //Массив вершин, в i-ой вершине i-ый ключ
- }
- Node* curr = &tree[0]; // curr указывает на верш с макс ключом с которой будем начинать поиск
- f(0, tree, n, curr);
- preorderTraversal(&tree[0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement