AlexandrTalchuk

Untitled

May 8th, 2020
90
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Найти среднее значение всех ключей дерева и найти строку, имеющую ближайшее к этому значению ключ
  2. #include<iostream>
  3. #include"conio.h"
  4. using namespace std;
  5.  
  6. struct Tree
  7. {
  8. int number;
  9. char* FIO;
  10. Tree* left, * right;
  11. };
  12.  
  13. void Add(Tree*& root, int num, char* fio);
  14. void Prefiks(Tree*& node);
  15. void Infiks(Tree*& node);
  16. void Postfiks(Tree*& node);
  17. void SearchbyKey(Tree*& node);
  18. void Balance(Tree*& p, Tree** arr, int n, int k);
  19. void Clear(Tree*& p);
  20. void Delete(Tree*& node, int inf);
  21. void Solution(Tree* p, int& value, int& counter);
  22. void closestNode(Tree*& root, int k);
  23.  
  24.  
  25. int main()
  26. {
  27. setlocale(LC_ALL, "rus");
  28. int choice, num, count=0, t=0,key=0,value=0,counter=0,srdn=0;
  29. char fio[36];
  30. Tree* root = nullptr;
  31. Tree** arr = new Tree * [count];
  32. while (true)
  33. {
  34. cout << "1.Добавить элемент в дерево\n2.Найти элемент по ключу\n3.Удалить элемент по ключу\n4.Сбалансировать дерево\n5.Префиксный просмотр (сверху вниз)\n6.Инфиксный просмотр (слева направо)\n7.Постфиксный просмотр (снизу вверх)\n8.Задание\n9.Выход" << endl;
  35. cin >> choice;
  36. switch (choice)
  37. {
  38. case 1:
  39. cout << "Введите ФИО: ";
  40. cin.ignore();
  41. cin.getline(fio, 36);
  42. cout << "Введите номер: ";
  43. cin >> num;
  44. Add(root, num, fio);
  45. break;
  46. case 2:
  47. SearchbyKey(root);
  48. _getch();
  49. break;
  50. case 3:
  51. cout << "Введите ключ";
  52. cin >> key;
  53. //Delete(root, key);
  54. break;
  55. case 4:
  56. Balance(root, arr, 0, count);
  57. cout << "Дерево сбалансированно" << endl;
  58. _getch();
  59. case 5:
  60. if (root == NULL)
  61. {
  62. cout << "Дерево пустое" << endl;
  63. }
  64. Prefiks(root);
  65. _getch();
  66. break;
  67. case 6:
  68. if (root == NULL)
  69. {
  70. cout << "Дерево пустое" << endl;
  71. }
  72. Infiks(root);
  73. _getch();
  74. break;
  75. case 7:
  76. if (root == NULL)
  77. {
  78. cout << "Дерево пустое" << endl;
  79. }
  80. Postfiks(root);
  81. _getch();
  82. break;
  83. case 8:
  84. Solution(root, value, counter);
  85. srdn = value / counter;
  86. cout << srdn << endl;
  87. suka(root,srdn);
  88.  
  89. _getch();
  90. break;
  91. case 9:
  92. cout << "Программа завершена" << endl;
  93. delete[] arr;
  94. Clear(root);
  95. break;
  96. default:
  97. cout << "Повторите еще раз" << endl;
  98. }
  99. system("cls");
  100. }
  101. }
  102. void Add(Tree*& root,int num,char* fio )
  103. {
  104. if (root == NULL)
  105. {
  106. root = new Tree;
  107. root->number = num;
  108. root->FIO = fio;
  109. root->left = root->right = NULL;
  110. }
  111. if (num > root->number)
  112. {
  113. Add(root->right, num, fio);
  114. }
  115. else if (num < root->number)
  116. {
  117. Add(root->left, num, fio);
  118. }
  119. }
  120.  
  121. void Prefiks(Tree*& node)
  122. {
  123. if (node != NULL)
  124. {
  125. cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
  126. Prefiks(node->left);
  127. Prefiks(node->right);
  128. }
  129.  
  130. }
  131.  
  132. void Infiks(Tree*& node)
  133. {
  134. if (node != NULL)
  135. {
  136. Infiks(node->left);
  137. cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
  138. Infiks(node->right);
  139. }
  140.  
  141. }
  142.  
  143. void Postfiks(Tree*& node)
  144. {
  145. if (node != NULL)
  146. {
  147. Postfiks(node->left);
  148. Postfiks(node->right);
  149. cout << "ФИО: " << node->FIO << ", " << "номер: " << node->number << endl;;
  150. }
  151.  
  152. }
  153.  
  154. void SearchbyKey(Tree*& node)
  155. {
  156. Tree* a = node;
  157. int key;
  158. bool search=false;
  159. cout << "Введите ключ" << endl;
  160. cin >> key;
  161. while (a != NULL)
  162. {
  163. if (a->number > key)
  164. {
  165. a = a->right;
  166. }
  167. else if (a->number < key)
  168. {
  169. a = a->left;
  170. }
  171. else
  172. {
  173. search = true;
  174. cout <<"ФИО: "<< a->FIO<<", "<<"Номер:"<<a->number << endl;
  175. break;
  176. }
  177. }
  178. if (!search)
  179. {
  180. cout<<"Такого ключа нет"<<endl;
  181. }
  182. }
  183.  
  184. void Balance(Tree*& p, Tree** arr, int n, int k)
  185. {
  186. if (n == k)
  187. {
  188. p = NULL;
  189. return;
  190. }
  191. else
  192. {
  193. int m = (n + k) / 2;
  194. p = arr[m];
  195. Balance(p->left, arr, n, m);
  196. Balance(p->right, arr, m + 1, k);
  197. }
  198. }
  199.  
  200. void Clear(Tree*& p)
  201. {
  202. if (p == NULL) return;
  203. Clear(p->left);
  204. Clear(p->right);
  205. delete(p);
  206. p = NULL;
  207. }
  208.  
  209. Tree* Delete(Tree* node, int inf)
  210. {
  211. Tree* ps = node,* pr = node, * w=nullptr, * v=nullptr;
  212. // Поиск удаляемого узла
  213. while ((ps != NULL) && (ps->number != inf))
  214. {
  215. pr = ps;
  216. if (inf < ps->number)
  217. {
  218. ps = ps->left;
  219. }
  220. else
  221. {
  222. ps = ps->right;
  223. }
  224. }
  225. if (ps == NULL)
  226. {
  227. return node; // Если узел не найден
  228. }
  229.  
  230. if ((ps->left == NULL) && (ps->right == NULL)) // Если узел не имеет дочерей
  231. {
  232. if (ps == pr) // Если это был последний элемент
  233. {
  234. delete(ps);
  235. return NULL;
  236. }
  237.  
  238. if (pr->left == ps) // Если удаляемый узел слева
  239. {
  240. pr->left = NULL;
  241. }
  242.  
  243. else // Если удаляемый узел справа
  244. {
  245. pr->right = NULL;
  246. }
  247.  
  248. delete(ps);
  249. return node;
  250. }
  251.  
  252. if (ps->left == NULL) // Если узел имеет дочь только справа
  253. {
  254. if (ps == pr)// Если удаляется корень
  255. {
  256. ps = ps->right;
  257. delete(pr);
  258. return ps;
  259. }
  260.  
  261. if (pr->left == ps) // Если удаляемый узел слева
  262. {
  263. pr->left = ps->right;
  264. }
  265.  
  266. else // Если удаляемый узел справа
  267. {
  268. pr->right = ps->right;
  269. }
  270.  
  271. delete(ps);
  272. return node;
  273. }
  274.  
  275. // Если узел имеет дочь только слева
  276. if (ps->right == NULL)
  277. {
  278. if (ps == pr) // Если удаляется корень
  279. {
  280. ps = ps->left;
  281. delete(pr);
  282. return ps;
  283. }
  284.  
  285. if (pr->left == ps) // Если удаляемый узел слева
  286. pr->left = ps->left;
  287. else // Если удаляемый узел справа
  288. pr->right = ps->left;
  289. delete(ps);
  290. return node;
  291. }
  292.  
  293. // Если узел имеет двух дочерей
  294. w = ps->left;
  295. if (w->right == NULL) // Если максимальный следует за ps
  296. {
  297. w->right = ps->right;
  298. }
  299.  
  300. else // Если максимальный не следует за ps
  301. {
  302. while (w->right != NULL)
  303. {
  304. v = w;
  305. w = w->right;
  306. }
  307. v->right = w->left;
  308. w->left = ps->left;
  309. w->right = ps->right;
  310. }
  311.  
  312. if (ps == pr) // Если удаляется корень
  313. { delete(ps);
  314. return w;
  315. }
  316.  
  317. if (pr->left == ps) // Если удаляемый узел слева
  318. {
  319. pr->left = w;
  320. }
  321.  
  322. else // Если удаляемый узел справа
  323. {
  324. pr->right = w;
  325. }
  326. delete(ps);
  327. return node;
  328. }
  329.  
  330. void Solution(Tree* r, int& value, int& counter)
  331. {
  332. if (r)
  333. {
  334. value += r->number; // записываем значение узла
  335. ++counter;
  336. Solution(r->left, value, counter);
  337. Solution(r->right, value, counter);
  338. }
  339.  
  340. }
  341.  
  342. void closestNode(Tree*& root, int sredn)
  343. {
  344. Tree* result = new Tree;
  345. if (root == NULL)
  346. {
  347. return;
  348. }
  349. if (result==NULL||abs(root->number - sredn) < abs(result->number - sredn))
  350. {
  351. result == root;
  352. }
  353. if (sredn < root->number)
  354. {
  355. closestNode(root->left, sredn);
  356. }
  357. else
  358. {
  359. closestNode(root->right, sredn);
  360. }
  361.  
  362. }
RAW Paste Data