API tools faq
paste
Advertisement
czlowiekzgon

Untitled

czlowiekzgon
Nov 4th, 2018
117
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.54 KB | None | 0 0
raw download clone embed print report
  1.  
  2.  
  3. #include "pch.h"
  4. #include <iostream>
  5. #include <sstream>
  6. #include <string>
  7. #include <cstdlib>
  8. #include <ctime>
  9. using namespace std;
  10.  
  11.  
  12. class Element {
  13.  
  14. private:
  15. int key;
  16. Element * ptr_left=nullptr;
  17. Element * ptr_right=nullptr;
  18.  
  19. public:
  20. Element();
  21. Element(int key_val);
  22. int get_key();
  23. Element * get_ptr_left();
  24. Element * get_ptr_right();
  25. void set_ptr_left(int liczba);
  26. void set_ptr_right(int liczba);
  27. void set_ptr_left(Element * ptr);
  28. void set_ptr_right(Element * ptr);
  29.  
  30.  
  31. };
  32. Element::Element() {
  33.  
  34. }
  35.  
  36. Element::Element(int key_val) {
  37. key = key_val;
  38.  
  39. }
  40.  
  41.  
  42.  
  43. int Element::get_key() {
  44. return key;
  45. }
  46.  
  47. Element * Element::get_ptr_left() {
  48. return ptr_left;
  49. }
  50.  
  51. Element * Element::get_ptr_right() {
  52. return ptr_right;
  53. }
  54.  
  55. void Element::set_ptr_left(int liczba) {
  56. ptr_left = new Element(liczba);
  57. }
  58.  
  59. void Element::set_ptr_right(int liczba) {
  60. ptr_right = new Element(liczba);
  61. }
  62.  
  63.  
  64. void Element::set_ptr_left(Element * ptr) {
  65. ptr_left = ptr;
  66. }
  67.  
  68. void Element::set_ptr_right(Element * ptr) {
  69. ptr_right = ptr;
  70. }
  71.  
  72. class Tree {
  73. private:
  74. Element * root = nullptr;
  75.  
  76. public:
  77. Tree();
  78. Tree(int i);
  79. void set_root(Element * ptr);
  80. void add(int key_val);
  81. void add_many(int num);
  82. bool find(int key_val,bool kom=true);
  83. void remove(int key_val);
  84. void show_pre_order();
  85. void show_pre_order(Element * ptr);
  86. void show_in_order();
  87. void show_in_order(Element * ptr);
  88. void show_post_order();
  89. void show_post_order(Element * ptr);
  90. };
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98. Tree::Tree() {
  99.  
  100. }
  101.  
  102. void Tree::set_root(Element * ptr) {
  103. root = ptr;
  104. }
  105.  
  106. bool Tree::find(int key_val, bool kom) {
  107. Element * sup_ptr = root;
  108. if(root==nullptr){
  109. if (kom == true) {
  110. cout << "korzen jest pusty" << endl;
  111.  
  112. }
  113. return false;
  114. }
  115. if (sup_ptr->get_key() == key_val) {
  116. if (kom == true) {
  117. cout << "istnieje element z podanym kluczem " << endl;
  118.  
  119. }
  120. return true;
  121. }
  122. else if (sup_ptr->get_key() > key_val) {
  123. sup_ptr = sup_ptr->get_ptr_left();
  124. }
  125. else if (sup_ptr->get_key() < key_val) {
  126. sup_ptr = sup_ptr->get_ptr_right();
  127. }
  128.  
  129. while (sup_ptr != nullptr) {
  130. if (sup_ptr->get_key() == key_val) {
  131. if (kom == true) {
  132. cout << "istnieje element z podanym kluczem " << endl;
  133. }
  134. return true;
  135. }
  136. else if (sup_ptr->get_key() > key_val) {
  137. sup_ptr = sup_ptr->get_ptr_left();
  138. }
  139. else if (sup_ptr->get_key() < key_val) {
  140. sup_ptr = sup_ptr->get_ptr_right();
  141. }
  142. }
  143. if (sup_ptr == nullptr) {
  144. if (kom == true) {
  145. cout << "nie ma elementu o podanym kluczu " << endl;
  146.  
  147. }
  148. return false;
  149. }
  150. }
  151.  
  152.  
  153. void Tree::add(int key_val) {
  154.  
  155. if (root == nullptr) {
  156. root = new Element(key_val);
  157. return;
  158.  
  159. }
  160.  
  161. bool czy_sie_powtarza = find(key_val,false);
  162. if (czy_sie_powtarza == true) {
  163. cout << "nie mozna dodac obikektu poniewaz istnieje juz jeden z takim kluczem" << endl;
  164. return;
  165. }
  166.  
  167. Element * sup_ptr = root;
  168.  
  169.  
  170. while ((sup_ptr->get_key() > key_val && sup_ptr->get_ptr_left() != nullptr) || (sup_ptr->get_key() < key_val && sup_ptr->get_ptr_right() != nullptr)) {
  171. if (sup_ptr->get_key() > key_val) {
  172. sup_ptr = sup_ptr->get_ptr_left();
  173. }
  174. else if (sup_ptr->get_key() < key_val) {
  175. sup_ptr = sup_ptr->get_ptr_right();
  176. }
  177.  
  178. }
  179. if (sup_ptr->get_key() > key_val) {
  180. sup_ptr->set_ptr_left(key_val);
  181. }
  182. else if (sup_ptr->get_key() < key_val) {
  183. sup_ptr->set_ptr_right(key_val);
  184. }
  185.  
  186. }
  187.  
  188. void Tree::add_many(int num) {
  189. for (int i = 0; i < num; i++) {
  190. int key_val = (rand() % 20)+0;
  191. while (find(key_val,false) == true) {
  192. key_val = (rand() % 20) + 0;
  193. }
  194. add(key_val);
  195. }
  196.  
  197. }
  198.  
  199.  
  200.  
  201. void Tree::show_pre_order(Element * ptr) {
  202. if (ptr == nullptr) {
  203. return;
  204. }
  205. else {
  206. cout << ptr->get_key() << endl;
  207. show_pre_order(ptr->get_ptr_left());
  208. show_pre_order(ptr->get_ptr_right());
  209. }
  210. }
  211.  
  212. void Tree::show_pre_order() {
  213. show_pre_order(root);
  214. }
  215.  
  216. void Tree::show_in_order(Element * ptr) {
  217. if (ptr == nullptr) {
  218. return;
  219. }
  220. else {
  221.  
  222. show_in_order(ptr->get_ptr_left());
  223. cout << ptr->get_key() << endl;
  224. show_in_order(ptr->get_ptr_right());
  225. }
  226. }
  227.  
  228. void Tree::show_in_order() {
  229. show_in_order(root);
  230. }
  231.  
  232.  
  233.  
  234. void Tree::show_post_order(Element * ptr) {
  235. if (ptr == nullptr) {
  236. return;
  237. }
  238. else {
  239.  
  240. show_post_order(ptr->get_ptr_left());
  241. show_post_order(ptr->get_ptr_right());
  242. cout << ptr->get_key() << endl;
  243. }
  244. }
  245.  
  246.  
  247. void Tree::show_post_order() {
  248. show_post_order(root);
  249. }
  250.  
  251.  
  252. void Tree::remove(int key_val) {
  253. Element * ptr = root;
  254. Element * par_ptr = nullptr;
  255. if (root == nullptr) {
  256. cout << "korzen jest pusty" << endl;
  257. return;
  258. }
  259. while (ptr != nullptr) {
  260.  
  261. if (ptr->get_key() == key_val) {
  262.  
  263. if (ptr->get_ptr_left() == nullptr && ptr->get_ptr_right() == nullptr) {
  264. if (par_ptr->get_ptr_left() == ptr) {
  265. delete ptr;
  266. par_ptr->set_ptr_left(nullptr);
  267. return;
  268. }
  269. else {
  270. delete ptr;
  271. par_ptr->set_ptr_right(nullptr);
  272. return;
  273. }
  274. }
  275.  
  276. else if (ptr->get_ptr_left() == nullptr && ptr->get_ptr_right() != nullptr) {
  277. if (par_ptr->get_ptr_left() == ptr) {
  278.  
  279. par_ptr->set_ptr_left(ptr->get_ptr_right());
  280. delete ptr;
  281. return;
  282. }
  283. else {
  284.  
  285. par_ptr->set_ptr_right(ptr->get_ptr_right());
  286. delete ptr;
  287. return;
  288. }
  289. }
  290. else if ((ptr->get_ptr_left() != nullptr && ptr->get_ptr_right() == nullptr)) {
  291. if (par_ptr->get_ptr_left() == ptr) {
  292.  
  293. par_ptr->set_ptr_left(ptr->get_ptr_left());
  294. delete ptr;
  295. return;
  296. }
  297. else {
  298.  
  299. par_ptr->set_ptr_left(ptr->get_ptr_right());
  300. delete ptr;
  301. return;
  302. }
  303. }
  304. else if ((ptr->get_ptr_left() != nullptr && ptr->get_ptr_right() != nullptr)) {
  305.  
  306.  
  307.  
  308. Element *succes_ptr = ptr->get_ptr_right();
  309. Element * par_succes_ptr = nullptr;
  310. while (succes_ptr->get_ptr_left() != nullptr) {
  311. par_succes_ptr = succes_ptr;
  312. succes_ptr = succes_ptr->get_ptr_left();
  313. }
  314. if (succes_ptr->get_ptr_right() == nullptr) {
  315. if (root == ptr && (ptr->get_ptr_right() == succes_ptr)) {
  316.  
  317. }
  318. else {
  319. par_succes_ptr->set_ptr_left(nullptr);
  320. }
  321.  
  322. }
  323. else {
  324. if (root == ptr && (ptr->get_ptr_right() == succes_ptr)) {
  325.  
  326. }
  327. else
  328. {
  329. par_succes_ptr->set_ptr_left(succes_ptr->get_ptr_right());
  330. }
  331.  
  332. }
  333.  
  334. succes_ptr->set_ptr_left(ptr->get_ptr_left());
  335. if (ptr == root && (ptr->get_ptr_right()==succes_ptr)) {
  336.  
  337. }
  338. else {
  339. succes_ptr->set_ptr_right(ptr->get_ptr_right());
  340. }
  341. if (ptr == root) {
  342. delete root;
  343. root = succes_ptr;
  344. return;
  345. }
  346.  
  347. if (par_ptr->get_ptr_left() == ptr) {
  348. par_ptr->set_ptr_left(succes_ptr);
  349. delete ptr;
  350. return;
  351. }
  352. else {
  353. par_ptr->set_ptr_right(succes_ptr);
  354. delete ptr;
  355. return;
  356. }
  357.  
  358.  
  359. }
  360.  
  361.  
  362. }
  363. else if (ptr->get_key() > key_val) {
  364. par_ptr = ptr;
  365. ptr = ptr->get_ptr_left();
  366. }
  367. else {
  368. par_ptr = ptr;
  369. ptr = ptr->get_ptr_right();
  370. }
  371. }
  372. cout << "nie mozna usunac wezla poniewaz nie istnieje " << endl;
  373. return;
  374. }
  375.  
  376.  
  377.  
  378.  
  379. int main()
  380. {
  381. srand(time(NULL));
  382.  
  383.  
  384. Tree tree;
  385.  
  386. tree.add(20);
  387. tree.add(10);
  388. tree.add(5);
  389. tree.add(30);
  390. tree.add(35);
  391. tree.add(40);
  392. tree.show_pre_order();
  393. tree.remove(30);
  394. cout << endl;
  395. tree.show_in_order();
  396.  
  397.  
  398. /*tree.add(10);
  399. tree.add(5);
  400. tree.add(4);
  401. tree.add(6);
  402. tree.add(15);
  403. tree.add(13);
  404. tree.add(16);
  405. tree.show();
  406. tree.remove(10);
  407. cout << endl;
  408. tree.show();*/
  409.  
  410.  
  411. /*tree.find(15);
  412. tree.find(5);
  413. tree.find(1);*/
  414. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!