SHARE
TWEET

Untitled

a guest Nov 19th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "pch.h"
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include "stdio.h"
  4. #include "stdlib.h"
  5. #include "time.h"
  6. #include <iostream>
  7.  
  8.  
  9. using namespace std;
  10.  
  11. struct drzewo
  12. {
  13.     int key;
  14.     drzewo *left, *right *parent;
  15.     char tab[10];
  16. };
  17.  
  18.  
  19. typedef struct drzewo *BST;
  20.  
  21. BST korzen = NULL; //TWORZENIE PUSTEGO DRZEWA
  22.  
  23.  
  24. int wstaw_element(BST korzen, int klucz) //zwrocenie wartosci innej niz 0 oznacza blad
  25. {
  26.  
  27.  
  28.     BST pom, previous, nowy;
  29.  
  30.     nowy = new struct drzewo;
  31.  
  32.    
  33.     nowy->left = NULL;
  34.  
  35.     nowy->right = NULL;
  36.  
  37.     nowy->key = klucz;
  38.  
  39.     previous = NULL;
  40.  
  41.     pom = korzen;
  42.  
  43.  
  44.     while (pom)
  45.     {
  46.         if (pom->key == klucz)
  47.         {
  48.             return(0); //el o tym kluczu już jest na liście
  49.         }
  50.  
  51.         previous = pom;
  52.  
  53.         if (pom->key > klucz)
  54.         {
  55.             pom = pom->left;
  56.         }
  57.         else
  58.             pom = pom->right;
  59.     }
  60.  
  61.  
  62.     if (!korzen)
  63.     {
  64.         korzen = nowy;
  65.         nowy->parent = NULL;
  66.     }
  67.  
  68.     else if (previous->key > klucz)
  69.     {
  70.         previous->left = nowy;
  71.         nowy->parent = previous;
  72.     }
  73.  
  74.     else
  75.     {
  76.         previous->right = nowy;
  77.         nowy->parent = previous;
  78.     }
  79.  
  80.  
  81.     return(1);
  82. }
  83. //DSW
  84. //prawo
  85. BST rotateLeft(BST previous,BST parent, BST wezel)
  86.  {
  87.   if (previous != NULL) //PREVIOUS = GRANDFATHER, WĘZEŁ = CHILD
  88.      {
  89.       if(previous->right = parent)
  90.       {
  91.           previous->right = wezel;
  92.       }
  93.       else
  94.       {
  95.          previous->left = wezel;
  96.       }
  97.       else
  98.       previous = wezel
  99.       nowy=wezel->right
  100.       wezel->right=parent
  101.       parent->left=nowy
  102.      }
  103.    
  104. }
  105. //lewo
  106. BST rotateRight(BST ,BST parent, BST wezel)
  107.  {
  108.   if (previous != NULL) //PREVIOUS = GRANDFATHER, WĘZEŁ = CHILD
  109.      {
  110.       if(previous->left = parent)
  111.       {
  112.           previous->left = wezel;
  113.       }
  114.       else
  115.       {
  116.          previous->right = wezel;
  117.       }
  118.       else
  119.       previous = wezel
  120.       nowy=wezel->left
  121.       wezel->left=parent
  122.       parent->right=nowy
  123.      }
  124.    
  125. }
  126.  
  127. BST makeBackbone(korzen)
  128. {
  129.     previous = NULL; //PREVIOUS = GRANDFATHER, WĘZEŁ = CHILD
  130.     nowy=korzen;
  131.     while(nowy!=NULL)
  132.     {
  133.         if((nowy->left)!=NULL)
  134.         {
  135.             nowy2=nowy->left;
  136.             rotateRight(previous, nowy, tmp->left);
  137.             nowy=nowy2;
  138.         }
  139.         else
  140.         {
  141.             previous=nowy;
  142.             nowy = tmp->left;
  143.         }
  144.     }
  145.    
  146. }
  147.  
  148. int maxWielkosc(BST korzen)  
  149. {  
  150.     if (korzen == NULL)  
  151.         return 0;  
  152.     else
  153.     {  
  154.         //dla każdego rozgałezienia
  155.         int lewaWielkosc = maxWielkosc(korzen->left);  
  156.         int prawaWielskoc = maxWielkosc(korzen->right);  
  157.      
  158.         //użycie tego większego
  159.         if (lewaWielkosc > prawaWielskoc)  
  160.             return(lewaWielkosc + 1);  
  161.         else return(prawaWielskoc + 1);  
  162.     }  
  163.    
  164. }
  165.  
  166. void wstawienieX1(int X1)
  167. {
  168.     int i, a;
  169.     int b;
  170.     for (i = 0; i < X1; i++)
  171.     {
  172.         a = ((rand() % (-999 - 222)) + -222);
  173.         do
  174.         {
  175.             a=((rand() % (-999 - 222)) + -222);
  176.            
  177.             b=wstaw_element(korzen, a);
  178.            
  179.         } while (b == 0);
  180.  
  181.     }
  182.  
  183. }
  184. void wstawienieX2(int X2)
  185. {
  186.     int i, a;
  187.     int b;
  188.     for (i = 0; i < X2; i++)
  189.     {
  190.         a = ((rand() % (-666 -999)) + -999);
  191.         do
  192.         {
  193.             a = ((rand() % (-666 -999)) + -999);
  194.            
  195.             b=wstaw_element(korzen, a);
  196.            
  197.         } while (b == 0);
  198.  
  199.     }
  200.  
  201. }  
  202.  
  203. void wstawienieX(int X)
  204. {
  205.     int i, a;
  206.     int b;
  207.     for (i = 0; i < X; i++)
  208.     {
  209.         a = ((rand() % (-10000 - 10000)) + -10000);
  210.         do
  211.         {
  212.             a = ((rand() % (-10000 - 10000)) + -10000);
  213.            
  214.             b=wstaw_element(korzen, a);
  215.            
  216.         } while (b == 0);
  217.  
  218.     }
  219.  
  220.    
  221. }
  222.  
  223.  
  224. BST wyszukiwanie(BST wezel, int klucz) //zwrocenie NULL oznacza, ze brak elementu
  225. {
  226.  
  227.  
  228.     while ((wezel != NULL) && (wezel->key != klucz))
  229.     {
  230.         if (klucz == wezel->key)
  231.         {
  232.             return wezel;
  233.         }
  234.         if (klucz < wezel->key)
  235.         {
  236.             wezel = wezel->left;
  237.  
  238.         }
  239.         else
  240.         {
  241.             wezel = wezel->right;
  242.  
  243.         }
  244.     }
  245.  
  246.  
  247.     return wezel;
  248. }
  249.  
  250. BST find_min(BST startowy)
  251. {
  252.     BST pom;
  253.     pom = startowy;
  254.  
  255.     while (pom->left)
  256.     {
  257.         pom = pom->left;
  258.     }
  259.     return (pom);
  260. }
  261.  
  262. BST find_max(BST startowy)
  263. {
  264.     BST pom;
  265.     pom = startowy;
  266.  
  267.     while (pom->right)
  268.     {
  269.         pom = pom->right;
  270.     }
  271.     return (pom);
  272. }
  273.  
  274.  
  275. BST find_successor(BST wezel) //szukanie następnika
  276. {
  277.     BST wezel_tmp;
  278.  
  279.     if (wezel->right != NULL)
  280.         return find_min(wezel->right);
  281.  
  282.     wezel_tmp = wezel->parent;
  283.  
  284.     while (wezel_tmp != NULL && wezel_tmp->left != wezel)
  285.     {
  286.         wezel = wezel_tmp;
  287.         wezel_tmp = wezel_tmp->parent;
  288.     }
  289.  
  290.     return wezel_tmp;
  291. }
  292.  
  293.  
  294. BST find_predecessor(BST wezel) // wszukanie poprzednika
  295. {
  296.     BST wezel_tmp;
  297.  
  298.     if (wezel->left != NULL)
  299.         return find_max(wezel->left);
  300.  
  301.     wezel_tmp = wezel->parent;
  302.  
  303.     while (wezel_tmp != NULL && wezel_tmp->right != wezel)
  304.     {
  305.         wezel = wezel_tmp;
  306.         wezel_tmp = wezel_tmp->parent;
  307.     }
  308.  
  309.     return wezel_tmp;
  310. }
  311.  
  312. //wersja odwolujaca sie do nastepnika
  313. int usuwanie_wezla(BST korzen, int klucz)
  314. {
  315.     BST usuwany, y, x;
  316.     usuwany = wyszukiwanie(korzen, klucz);
  317.  
  318.     if (!usuwany) return (-1); // blad - nie ma el o tym kluczu
  319.  
  320.     if (usuwany->left == NULL || usuwany->right == NULL)
  321.     {
  322.         y = usuwany;
  323.     }
  324.     else
  325.         y = find_successor(usuwany);
  326.  
  327.     if (y->left != NULL)
  328.     {
  329.         x = y->left;
  330.     }
  331.     else
  332.     {
  333.         x = y->right;
  334.     }
  335.  
  336.     if (x != NULL)
  337.         x->parent = y->parent;
  338.  
  339.     if (y->parent == NULL)
  340.     {
  341.         korzen = x;
  342.     }
  343.     else
  344.     {
  345.         if ( y == y->parent->left)
  346.             y->parent->left = x;
  347.         else
  348.             y->parent->right = x;
  349.     }
  350.  
  351.     if (y != usuwany)
  352.     {
  353.         usuwany->key = y->key;
  354.     }
  355.  
  356.     delete y;
  357.     return 0;
  358. }
  359.  
  360. //przechodzenie drzewa w trybie inorder
  361. void inorder(BST korzen)
  362. {
  363.     if (korzen != NULL)
  364.     {
  365.         inorder(korzen->left);
  366.         cout << korzen->key << "";
  367.         inorder(korzen->right);
  368.         cout << korzen;
  369.     }
  370.  
  371. }
  372.  
  373. void preorder(BST korzen)
  374. {
  375.     if (korzen != NULL)
  376.     {
  377.         cout << korzen->key << " ";
  378.         preorder(korzen->left);
  379.         preorder(korzen->right);
  380.  
  381.     }
  382.  
  383. }
  384. //--------------------------------------------------------------------------
  385. int main()
  386. {
  387.     srand(time(NULL));
  388.  
  389.     clock_t begin, end;
  390.     double time_spent;     // czas start
  391.     begin = clock();
  392.  
  393.     int X, k1, k2, k3, k4;  // liczba elementĂłw do wylosowania X i nastÄ™pnie wartoĹ›ci czterech kluczy k1, k2, k3, k4
  394.     FILE* fp = fopen("inlab04.txt", "r");
  395.     if (fp == NULL)
  396.         return -1;
  397.     fscanf(fp, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4);  // wczytanie pliku
  398.     fclose(fp);
  399.  
  400.     int X1,X2; // liczba elementĂłw do wylosowania X i nastÄ™pnie wartoĹ›ci czterech kluczy k1, k2, k3, k4
  401.     FILE* fp = fopen("inlab05.txt", "r");
  402.     if (fp == NULL)
  403.         return -1;
  404.     fscanf(fp, "%d %d", &X1, &X2);  // wczytanie pliku
  405.     fclose(fp);
  406.  
  407.  
  408.  
  409.  
  410.     usuwanie_wezla(korzen, k1);
  411.     wstaw_element(korzen, k1);
  412.     wstawienieX(X);
  413.     inorder(korzen);
  414.     preorder(korzen);
  415.     wstaw_element(korzen, k2);
  416.     inorder(korzen);
  417.     wstaw_element(korzen, k3);
  418.     wstaw_element(korzen, k4);
  419.     usuwanie_wezla(korzen, k1);
  420.     wyszukiwanie(korzen, k1);
  421.     usuwanie_wezla(korzen, k2);
  422.     usuwanie_wezla(korzen, k3);
  423.     usuwanie_wezla(korzen, k4);
  424.  
  425.     cout << endl;
  426.  
  427.     cout << k1 << endl;
  428.     cout << k2 << endl;
  429.     cout << k3 << endl;
  430.     cout << k4 << endl;
  431.  
  432.     end = clock();
  433.     time_spent = (double)(end - begin) / CLOCKS_PER_SEC;  // czas stop
  434.  
  435.     printf("\n\n\n czas wykonania = %g ", time_spent);
  436.     printf("\n\n\n");
  437.     system("pause");
  438.     return 0;
  439. }
RAW Paste Data
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
 
Top