Guest User

Untitled

a guest
Dec 8th, 2019
95
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //ALGO2 N1 20B LAB04
  2. //Maciej Baraniecki
  3. //bm35988@zut.edu.pl
  4.  
  5.  
  6. #include <iostream>
  7. #include <string>
  8. #include <cstdlib>
  9. #include <ctime>
  10. #include <stdio.h>
  11.  
  12. using namespace std;
  13.  
  14. struct BSTNode
  15. {
  16. int klucz;
  17. struct BSTNode *left, *right;
  18. char tab[10];
  19.  
  20. };
  21.  
  22. /*BSTNode* newNode(int klucz)
  23. {
  24. BSTNode* temp = new BSTNode;
  25. temp->klucz = klucz;
  26. temp->left=temp->right = NULL;
  27. return temp;
  28. }*/
  29.  
  30.  
  31. bool dodaj(BSTNode* root, int klucz)
  32. {
  33. BSTNode* p = root;
  34. BSTNode* prev=nullptr;
  35.  
  36. while(p!=nullptr)
  37. {
  38. prev=p;
  39. if(p->klucz<klucz)
  40. {
  41. p=p->right;
  42. }
  43. else
  44. {
  45. p=p->left;
  46. }
  47.  
  48. }
  49.  
  50. if(root->klucz==0)
  51. {
  52. //root=new BSTNode;
  53. root->klucz=klucz;
  54. root->left=nullptr;
  55. root->right=nullptr;
  56. cout<<"Dodano korzen"<<endl;
  57. return true;
  58. }
  59. else if(prev->klucz<klucz)
  60. {
  61. prev->right=new BSTNode;
  62. (prev->right)->klucz=klucz;
  63. (prev->right)->left=nullptr;
  64. (prev->right)->right=nullptr;
  65. cout<<"Dodano wezel prawy"<<endl;
  66. return true;
  67. }
  68. else if(prev->klucz>klucz)
  69. {
  70. prev->left=new BSTNode;
  71. (prev->left)->klucz=klucz;
  72. (prev->left)->left=nullptr;
  73. (prev->left)->right=nullptr;
  74. cout<<"Dodano wezel lewy"<<endl;
  75. return true;
  76. }
  77. else
  78. {
  79. return false;
  80. }
  81.  
  82.  
  83. };
  84.  
  85. void wstawianie(BSTNode* root, int X)
  86. {
  87. int klucz;
  88. for (int i = 0; i < X; i++)
  89. {
  90. do
  91. {
  92. klucz = (rand() % 20000) - 1000;
  93. }while(dodaj(root,klucz)!=true);
  94. }
  95. }
  96.  
  97. BSTNode* search(BSTNode* root, int klucz)
  98. {
  99. BSTNode* p = root;
  100. if(!p)
  101. {
  102. cout<<"Drzewo puste!"<<endl;
  103. return nullptr;
  104. }
  105. while((p==nullptr)&(klucz==p->klucz))
  106. {
  107. if(p->klucz<klucz)
  108. {
  109. cout<<"NIE"<<endl;
  110. p=p->right;
  111. }
  112. else
  113. {
  114. cout<<"TAK"<<endl;
  115. p=p->left;
  116. }
  117. }
  118. cout<<"ZNaleziono"<<endl;
  119. return(p);
  120.  
  121. }
  122.  
  123. BSTNode* minValueNode(BSTNode* node)
  124. {
  125. BSTNode* current = node;
  126.  
  127. /* loop down to find the leftmost leaf */
  128. while (current->left != nullptr)
  129. current = current->left;
  130.  
  131. return current;
  132. }
  133.  
  134.  
  135. BSTNode* usun(BSTNode* root, int klucz)
  136. {
  137. if(root == NULL)
  138. {
  139. return root;
  140. }
  141.  
  142. if(klucz < root->klucz)
  143. {
  144. root->left = usun(root->left,klucz);
  145. }
  146. else if(klucz > root->klucz)
  147. {
  148. root->right = usun(root->right, klucz);
  149. }
  150. else
  151. {
  152. if(root->left == NULL)
  153. {
  154. BSTNode* temp = root->right;
  155. delete(root);
  156. return temp;
  157. }
  158. else if(root->right == NULL)
  159. {
  160. BSTNode* temp = root->left;
  161. delete(root);
  162. return temp;
  163. }
  164.  
  165. BSTNode* temp=minValueNode(root->right);
  166.  
  167. root->klucz = temp->klucz;
  168.  
  169. root->right = usun(root->right, temp->klucz);
  170.  
  171. }
  172. return root;
  173.  
  174.  
  175.  
  176. }
  177.  
  178. BSTNode* usuwaj(BSTNode* root){ //pierwszy argument to head
  179. if (root->left)
  180. usuwaj(root->left);
  181. if (root->right)
  182. usuwaj(root->right);
  183. delete(root);
  184. if (root)
  185. root = NULL;
  186.  
  187.  
  188. return NULL;
  189. }
  190.  
  191.  
  192.  
  193.  
  194. void preorder(BSTNode* root)
  195. {
  196. int liczba = 0;
  197. {
  198. if (root == NULL)
  199. return;
  200. cout << "PREORDER-------------------------- ";
  201. cout << root->klucz << " "<<endl;
  202. liczba++;
  203.  
  204. preorder(root->left);
  205. preorder(root->right);
  206. }
  207.  
  208. }
  209.  
  210.  
  211. void inorder(BSTNode * root)
  212. {
  213. if (root)
  214. {
  215. inorder(root->left);
  216. cout << "INORDER------------------------ ";
  217. cout << root->klucz << endl; // tutaj przetwarzamy bieżący węzeł
  218. inorder(root->right);
  219. }
  220. }
  221.  
  222.  
  223. void postorder(BSTNode* root)
  224. {
  225. if (root == NULL)
  226. return;
  227. postorder(root->left);
  228. postorder(root->right);
  229. cout << root->klucz << " ";
  230. }
  231.  
  232.  
  233. BSTNode* rotate_right(BSTNode* root, BSTNode* grandfather, BSTNode* parent, BSTNode* child)
  234. {
  235. BSTNode* tmp;
  236. if (grandfather){
  237. if (grandfather->right == parent){
  238. grandfather->right = child;
  239. }
  240. else{
  241. grandfather->left = child;
  242. }
  243. }
  244. else
  245. root = child;
  246.  
  247. if (parent->left == child){
  248. tmp = child->right;
  249. child->right = parent;
  250. parent->left = tmp;
  251. }
  252. else{
  253. tmp = child->right;
  254. child->left = parent;
  255. parent->right = tmp;
  256. }
  257.  
  258. return root;
  259.  
  260.  
  261. }
  262.  
  263. BSTNode* rotate_left(BSTNode* root, BSTNode* grandfather, BSTNode* parent, BSTNode* child)
  264. {
  265. BSTNode* tmp;
  266. if (grandfather){
  267. if (grandfather->right == parent){
  268. grandfather->right = child;
  269. }
  270. else{
  271. grandfather->left = child;
  272. }
  273. }
  274. else
  275. root = child;
  276.  
  277. if (parent->right == child){
  278. tmp = child->left;
  279. child->left = parent;
  280. parent->right = tmp;
  281. }
  282. else{
  283. tmp = child->left;
  284. child->right = parent;
  285. parent->left = tmp;
  286. }
  287.  
  288. return root;
  289. }
  290.  
  291. BSTNode* make_backbone(BSTNode* root)
  292. {
  293. BSTNode* grandfather=NULL;
  294. BSTNode* tmp=root;
  295. while(tmp!=NULL)
  296. {
  297. if((tmp->left)!=NULL)
  298. {
  299. BSTNode* tmp2 = tmp->left;
  300. root=rotate_right(root,grandfather,tmp,tmp->left);
  301. tmp=tmp2;
  302. }
  303. else
  304. {
  305. grandfather=tmp;
  306. tmp=tmp->right;
  307. }
  308. }
  309. return root;
  310. }
  311.  
  312. BSTNode* make_perfect_tree(BSTNode* root,int N)
  313. {
  314. BSTNode* grandfather=NULL;
  315. BSTNode* tmp=root;
  316. BSTNode* tmp2;
  317. int m=1;
  318. while(m<=N)
  319. {
  320. m=2*m+1;
  321. }
  322. m=m/2;
  323. for(int i=0;i<(N-m);i++)
  324. {
  325. tmp2=tmp->right;
  326. if(tmp2!=NULL)
  327. {
  328. root=rotate_left(root, grandfather,tmp,tmp->right);
  329. grandfather=tmp2;
  330. tmp=tmp2->right;
  331. }
  332. }
  333. while(m>1)
  334. {
  335. m=m/2;
  336. grandfather=NULL;
  337. tmp=root;
  338. for(int j=0;j<m;j++)
  339. {
  340. tmp2=tmp->right;
  341. root=rotate_left(root, grandfather,tmp,tmp->right);
  342. grandfather=tmp2;
  343. tmp=tmp2->right;
  344. }
  345. }
  346. return root;
  347. }
  348.  
  349. int maxDepth(BSTNode* root)
  350. {
  351. if (root == NULL)
  352. return 0;
  353. else
  354. {
  355. int lDepth = maxDepth(root->left);
  356. int rDepth = maxDepth(root->right);
  357. if (lDepth > rDepth)
  358. return(lDepth + 1);
  359. else return(rDepth + 1);
  360. }
  361. }
  362.  
  363.  
  364. int main()
  365. {
  366. int k1, k2, k3, k4;
  367. int X;
  368. /*#pragma warning(disable : 4996)
  369. FILE* fp = fopen("inlab03.txt", "r");
  370. if (fp == NULL)
  371. return -1;
  372. fscanf(fp, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4); // wczytanie pliku
  373. fclose(fp);*/
  374.  
  375. k1=45;
  376. k2=245;
  377. k3=1;
  378. k4=4;
  379. X=400;
  380. int N;
  381.  
  382.  
  383. //czas start
  384.  
  385. clock_t begin, end;
  386. double time_spent;
  387. srand((unsigned int)time(NULL));
  388. begin = clock();
  389. BSTNode* root=new BSTNode;
  390.  
  391. /*dodaj(root,15);
  392. dodaj(root,10);
  393. dodaj(root,25);
  394. dodaj(root,5);
  395. dodaj(root,13);
  396. dodaj(root,20);
  397. dodaj(root,33);
  398. dodaj(root,22);
  399. dodaj(root,24);
  400. inorder(root);
  401.  
  402. usun(root,33);
  403. //cout << "root:" << root << " " << root->klucz<<endl;
  404. inorder(root);
  405.  
  406. int wysokosc=maxDepth(root);
  407. cout<<"Wysokosc drzewa:"<<wysokosc<<endl;*/
  408.  
  409.  
  410.  
  411. //inicjacja pustego drzewa
  412. //BSTNode* root=new BSTNode;// = new BSTNode;
  413. //root->right=nullptr;
  414. //root->left=nullptr;
  415. //root=dodaj(root,((rand() % 20000) - 1000));
  416.  
  417. //usuń element o wartości klucza k1;
  418. cout << "Usuwanie elementu o wartosci klucza k1..." << endl;
  419. usun(root, k1);
  420. //wstaw element o wartości klucza k1;
  421. cout << "Dodawanie elementu o wartosci klucza k1..." << endl;
  422.  
  423. dodaj(root, k1);
  424. //cout << root << endl;
  425. //wstaw X elementów do drzewa;
  426. cout << "Wstawianie X elementow do drzewa..." << endl;
  427. wstawianie(root, X);
  428. //wyświetl wszystkie klucze w trybie inorder;
  429. cout << "Przejscie w trybie inorder..." << endl;
  430. //inorder(root);
  431. //wyświetl wszystkie klucze w trybie preorder;
  432. cout << "Przejscie w trybie preorder..." << endl;
  433. //preorder(root);
  434. //wstaw element o wartości klucza k2;
  435. cout << "Dodawanie elementu o wartosci klucza k2..." << endl;
  436. dodaj(root, k2);
  437. //wyświetl wszystkie klucze w trybie inorder;
  438. cout << "Przejscie w trybie inorder..." << endl;
  439. //inorder(root);
  440. //wstaw element o wartości klucza k3;
  441. cout << "Dodawanie elementu o wartosci klucza k3..." << endl;
  442. dodaj(root, k3);
  443. //wstaw element o wartości klucza k4;
  444. cout << "Dodawanie elementu o wartosci klucza k4..." << endl;
  445. dodaj(root, k4);
  446. //usuń element o wartości klucza k1;
  447. cout << "Usuwanie elementu o wartosci klucza k1..." << endl;
  448. inorder(root);
  449. usun(root, k1);
  450. //wyświetl wszystkie klucze w trybie preorder;
  451. cout << "Przejscie w trybie preorder..." << endl;
  452. preorder(root);
  453. //wyszukaj element o wartości k1;
  454. cout << "Wyszukanie elementu o wartosci klucza k1..." << endl;
  455. search(root, k1);
  456. //usuń element o wartości klucza k2;
  457. cout << "Usuwanie elementu o wartosci klucza k2..." << endl;
  458. usun(root, k2);
  459. //wyświetl wszystkie klucze w trybie inorder;
  460. cout << "Przejscie w trybie inorder" << endl;
  461. //inorder(root);
  462. //usuń element o wartości klucza k3;
  463. cout << "Usuwanie elementu o wartosci klucza k3..." << endl;
  464. usun(root, k3);
  465. //usuń element o wartości klucza k4;
  466. cout << "Usuwanie elementu o wartosci klucza k4..." << endl;
  467. usun(root, k4);
  468. inorder(root);
  469. cout<<endl;
  470. //dodaj(root,4);
  471. //dodaj(root,4);
  472. inorder(root);
  473. int wysokosc=maxDepth(root);
  474. cout<<"Wysokosc drzewa:"<<wysokosc<<endl;
  475. root=make_backbone(root);
  476. wysokosc=maxDepth(root);
  477. cout<<"Wysokosc drzewa (lista):"<<wysokosc<<endl;
  478. root=make_perfect_tree(root,wysokosc);
  479. wysokosc=maxDepth(root);
  480. cout<<"Wysokosc drzewa po DSW:"<<wysokosc<<endl;
  481. usuwaj(root);
  482. root=new BSTNode;
  483.  
  484. //czas stop;
  485.  
  486. end = clock();
  487. time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  488.  
  489. //wypisz czas wykonania;
  490. cout << "Czas wykonania:" << time_spent << endl;
  491.  
  492. //cout << "root:" << root << " " << root->klucz<<endl;
  493.  
  494. }
RAW Paste Data