Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Найти среднее значение всех ключей дерева и найти строку, имеющую ближайшее к этому значению ключ
- #include<iostream>
- #include"conio.h"
- using namespace std;
- struct Tree
- {
- int number;
- char* FIO;
- Tree* left, * right;
- };
- void Add(Tree*& root, int num, char* fio);
- void Prefiks(Tree*& node);
- void Infiks(Tree*& node);
- void Postfiks(Tree*& node);
- void SearchbyKey(Tree*& node);
- void Balance(Tree*& p, Tree** arr, int n, int k);
- void Clear(Tree*& p);
- void Delete(Tree*& node, int inf);
- void Solution(Tree* p, int& value, int& counter);
- void closestNode(Tree*& root, int k);
- int main()
- {
- setlocale(LC_ALL, "rus");
- int choice, num, count=0, t=0,key=0,value=0,counter=0,srdn=0;
- char fio[36];
- Tree* root = nullptr;
- Tree** arr = new Tree * [count];
- while (true)
- {
- cout << "1.Добавить элемент в дерево\n2.Найти элемент по ключу\n3.Удалить элемент по ключу\n4.Сбалансировать дерево\n5.Префиксный просмотр (сверху вниз)\n6.Инфиксный просмотр (слева направо)\n7.Постфиксный просмотр (снизу вверх)\n8.Задание\n9.Выход" << endl;
- cin >> choice;
- switch (choice)
- {
- case 1:
- cout << "Введите ФИО: ";
- cin.ignore();
- cin.getline(fio, 36);
- cout << "Введите номер: ";
- cin >> num;
- Add(root, num, fio);
- break;
- case 2:
- SearchbyKey(root);
- _getch();
- break;
- case 3:
- cout << "Введите ключ";
- cin >> key;
- //Delete(root, key);
- break;
- case 4:
- Balance(root, arr, 0, count);
- cout << "Дерево сбалансированно" << endl;
- _getch();
- case 5:
- if (root == NULL)
- {
- cout << "Дерево пустое" << endl;
- }
- Prefiks(root);
- _getch();
- break;
- case 6:
- if (root == NULL)
- {
- cout << "Дерево пустое" << endl;
- }
- Infiks(root);
- _getch();
- break;
- case 7:
- if (root == NULL)
- {
- cout << "Дерево пустое" << endl;
- }
- Postfiks(root);
- _getch();
- break;
- case 8:
- Solution(root, value, counter);
- srdn = value / counter;
- cout << srdn << endl;
- suka(root,srdn);
- _getch();
- break;
- case 9:
- cout << "Программа завершена" << endl;
- delete[] arr;
- Clear(root);
- break;
- default:
- cout << "Повторите еще раз" << endl;
- }
- system("cls");
- }
- }
- void Add(Tree*& root,int num,char* fio )
- {
- if (root == NULL)
- {
- root = new Tree;
- root->number = num;
- root->FIO = fio;
- root->left = root->right = NULL;
- }
- if (num > root->number)
- {
- Add(root->right, num, fio);
- }
- else if (num < root->number)
- {
- Add(root->left, num, fio);
- }
- }
- void Prefiks(Tree*& node)
- {
- if (node != NULL)
- {
- cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
- Prefiks(node->left);
- Prefiks(node->right);
- }
- }
- void Infiks(Tree*& node)
- {
- if (node != NULL)
- {
- Infiks(node->left);
- cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
- Infiks(node->right);
- }
- }
- void Postfiks(Tree*& node)
- {
- if (node != NULL)
- {
- Postfiks(node->left);
- Postfiks(node->right);
- cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
- }
- }
- void SearchbyKey(Tree*& node)
- {
- Tree* a = node;
- int key;
- bool search=false;
- cout << "Введите ключ" << endl;
- cin >> key;
- while (a != NULL)
- {
- if (a->number > key)
- {
- a = a->right;
- }
- else if (a->number < key)
- {
- a = a->left;
- }
- else
- {
- search = true;
- cout <<"ФИО: "<< a->FIO<<", "<<"Номер:"<<a->number << endl;
- break;
- }
- }
- if (!search)
- {
- cout<<"Такого ключа нет"<<endl;
- }
- }
- void Balance(Tree*& p, Tree** arr, int n, int k)
- {
- if (n == k)
- {
- p = NULL;
- return;
- }
- else
- {
- int m = (n + k) / 2;
- p = arr[m];
- Balance(p->left, arr, n, m);
- Balance(p->right, arr, m + 1, k);
- }
- }
- void Clear(Tree*& p)
- {
- if (p == NULL) return;
- Clear(p->left);
- Clear(p->right);
- delete(p);
- p = NULL;
- }
- Tree* Delete(Tree* node, int inf)
- {
- Tree* ps = node,* pr = node, * w=nullptr, * v=nullptr;
- // Поиск удаляемого узла
- while ((ps != NULL) && (ps->number != inf))
- {
- pr = ps;
- if (inf < ps->number)
- {
- ps = ps->left;
- }
- else
- {
- ps = ps->right;
- }
- }
- if (ps == NULL)
- {
- return node; // Если узел не найден
- }
- if ((ps->left == NULL) && (ps->right == NULL)) // Если узел не имеет дочерей
- {
- if (ps == pr) // Если это был последний элемент
- {
- delete(ps);
- return NULL;
- }
- if (pr->left == ps) // Если удаляемый узел слева
- {
- pr->left = NULL;
- }
- else // Если удаляемый узел справа
- {
- pr->right = NULL;
- }
- delete(ps);
- return node;
- }
- if (ps->left == NULL) // Если узел имеет дочь только справа
- {
- if (ps == pr)// Если удаляется корень
- {
- ps = ps->right;
- delete(pr);
- return ps;
- }
- if (pr->left == ps) // Если удаляемый узел слева
- {
- pr->left = ps->right;
- }
- else // Если удаляемый узел справа
- {
- pr->right = ps->right;
- }
- delete(ps);
- return node;
- }
- // Если узел имеет дочь только слева
- if (ps->right == NULL)
- {
- if (ps == pr) // Если удаляется корень
- {
- ps = ps->left;
- delete(pr);
- return ps;
- }
- if (pr->left == ps) // Если удаляемый узел слева
- pr->left = ps->left;
- else // Если удаляемый узел справа
- pr->right = ps->left;
- delete(ps);
- return node;
- }
- // Если узел имеет двух дочерей
- w = ps->left;
- if (w->right == NULL) // Если максимальный следует за ps
- {
- w->right = ps->right;
- }
- else // Если максимальный не следует за ps
- {
- while (w->right != NULL)
- {
- v = w;
- w = w->right;
- }
- v->right = w->left;
- w->left = ps->left;
- w->right = ps->right;
- }
- if (ps == pr) // Если удаляется корень
- { delete(ps);
- return w;
- }
- if (pr->left == ps) // Если удаляемый узел слева
- {
- pr->left = w;
- }
- else // Если удаляемый узел справа
- {
- pr->right = w;
- }
- delete(ps);
- return node;
- }
- void Solution(Tree* r, int& value, int& counter)
- {
- if (r)
- {
- value += r->number; // записываем значение узла
- ++counter;
- Solution(r->left, value, counter);
- Solution(r->right, value, counter);
- }
- }
- void closestNode(Tree*& root, int sredn)
- {
- Tree* result = new Tree;
- if (root == NULL)
- {
- return;
- }
- if (result==NULL||abs(root->number - sredn) < abs(result->number - sredn))
- {
- result == root;
- }
- if (sredn < root->number)
- {
- closestNode(root->left, sredn);
- }
- else
- {
- closestNode(root->right, sredn);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement