Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct Node
- {
- int key;
- int idx;
- Node* left;
- Node* right;
- Node* parent;
- };
- void find_parent(int* l, int* r, int idx, Node* tree, int max_l, int max_r)
- {
- int idx_left = *l;
- int idx_right = *r;
- bool is_greater = tree[0].key <= tree[idx].key;
- Node* curr;
- is_greater ? curr = &tree[idx_right] : curr = &tree[idx_left];
- if (curr->key <= tree[idx].key && curr->right == NULL)
- {
- tree[idx].parent = curr;
- curr->right = &tree[idx];
- cout << " parent finded " << endl;
- if (is_greater & tree[idx].key > max_r)
- {
- * r = idx;
- std::cout << "new max right =" << tree[idx].key << std::endl;
- }
- if (!is_greater & tree[idx].key > max_l)
- {
- std::cout << "old max left =" << max_l << " ";
- * l = idx;
- std::cout << ", new max left =" << tree[idx].key << "idx = " << idx << std::endl;
- }
- }
- else if (curr->key > tree[idx].key)
- {
- is_greater ? * r = tree[idx_right].left->idx : * l = tree[idx_left].left->idx;
- find_parent(l, r, idx, tree, max_l, max_r);
- }
- else if (curr->right != NULL)
- {
- is_greater ? * r = tree[idx_right].right->idx : * l = tree[idx_left].right->idx;
- find_parent(l, r, idx, tree, max_l, max_r);
- }
- return;
- }
- void f(int* idx_left, int* idx_right, int k, Node* tree, int n)
- {
- int max_l, max_r;
- (*idx_left == 0) ? max_l = -1: max_l = tree[*idx_left].key;
- (*idx_right == 0) ? max_r = -1: max_r = tree[*idx_right].key;
- cout << "Вызов от " << tree[k].key << endl;
- std::cout << "max left =" << max_l << " idx = " << *idx_left << " ";
- std::cout << "max right =" << max_r << " ";
- cout << endl;
- while (k < n - 1 & tree[k + 1].key < tree[k].key)
- {
- tree[k].left = &tree[k + 1];
- tree[k + 1].parent = &tree[k];
- k++;
- }
- //либо k = n-1, то есть осталась одна вершина - ничего не надо делать
- //либо k+1 -ый нарушает убывание - вызвать функцию поиска родителя
- //либо и то и то
- if (k + 1 < n)
- {
- cout << "Сейчас запущу поиск родителя для " << tree[k+1].key << endl;
- std::cout << "до запуска max left =" << max_l << " idx = " << *idx_left << " ";
- std::cout << "до запуска max right =" << max_r << " ";
- cout << endl;
- find_parent(idx_left, idx_right, k + 1, tree, max_l, max_r);
- }
- //После вставки нарушителя (k+1-го) могут остаться еще вершины и надо запустить снова с k+1-го
- if (k + 2 < n)
- {
- cout << "Ещё не конец, запущу от " << tree[k+1].key << endl;
- std::cout << "до запуска max left =" << max_l << " idx = " << *idx_left << " ";
- std::cout << "до запуска max right =" << max_r << " ";
- cout << endl;
- f(idx_left, idx_right, k + 1, tree, n);
- }
- }
- void preorderTraversal(Node* x)
- {
- if (x != NULL)
- {
- std::cout << x->key << " ";
- preorderTraversal(x->left);
- preorderTraversal(x->right);
- }
- return;
- }
- void inorderTraversal(Node* x)
- {
- if (x != NULL)
- {
- inorderTraversal(x->left);
- std::cout << x->key << " ";
- inorderTraversal(x->right);
- }
- return;
- }
- void postorderTraversal(Node* x)
- {
- if (x != NULL)
- {
- postorderTraversal(x->left);
- postorderTraversal(x->right);
- std::cout << x->key << " ";
- }
- return;
- }
- void print_tree(Node* tree, int n)
- {
- std::cout << std::endl;
- for (int i = 0; i < n; ++i)
- {
- std::cout << "i= " << tree[i].key << ": ";
- if (tree[i].left != NULL)
- std::cout << tree[i].left->key << " ";
- if (tree[i].right != NULL)
- std::cout << tree[i].right->key << " ;";
- std::cout << std::endl;
- }
- std::cout << std::endl;
- }
- int main()
- {
- int n;
- std::cin >> n;
- int idx_left = 0, idx_right = 0;
- Node tree[n];
- for (int i = 0; i < n; ++i)
- {
- tree[i].right = NULL;
- tree[i].left = NULL;
- tree[i].parent = NULL;
- tree[i].idx = i;
- std::cin >> tree[i].key;
- }
- f(&idx_left, &idx_right, 0, tree, n);
- print_tree(tree, n);
- postorderTraversal(&tree[0]);
- std::cout << std::endl;
- inorderTraversal(&tree[0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement