fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <sys/time.h>
  4.  
  5. struct wezel
  6. {
  7.     int wartosc;
  8.     int ilosc_kluczy;
  9.     char kolor;
  10.     struct wezel *rodzic;
  11.     struct wezel *l_syn;
  12.     struct wezel *p_syn;
  13. }*root;
  14.  
  15. //funkcja zwraca wskaznik elementu o najmniejszej wartosci (najbardziej na lewo)
  16. struct wezel* naj_lewo(struct wezel *start)
  17. {
  18. if(start->l_syn != NULL)
  19. return naj_lewo(start->l_syn);
  20. else
  21. return start;
  22. }
  23.  
  24. //funkcja zwraca wezel o podanej wartosci, badz NULL, gdy taki wezel nie istnieje
  25. struct wezel* szukaj(struct wezel *start, int wartosc)
  26. {
  27. //jezeli wezel ma szukana wartosc to odnalezlismy go
  28.     if (start->wartosc == wartosc) return start;
  29. //jezeli szukana wartosc jest mniejsza to szukamy w lewym poddrzewie o ile istnieje
  30.     else if (wartosc < start->wartosc && start->l_syn != NULL) return szukaj(start->l_syn, wartosc);
  31. //jezeli szukana wartosc jest wieksza to szukamy w prawym poddrzewie o ile istnieje
  32.     else if (wartosc > start->wartosc && start->p_syn != NULL) return szukaj(start->p_syn, wartosc);
  33.     return NULL;
  34. }
  35.  
  36. //dodaje wezel o podanej wartosci n, do drzewa o korzeniu start
  37. int dodawanie(int n, struct wezel *start)
  38. {
  39. //jeżeli dany węzeł nie istnieje, to dodaj taki do drzewa, w przeciwnym wypadku dodajemy do ilosc_kluczy +1
  40.  
  41. //jezeli drzewo jest puste to dodaj korzen
  42.     if (root == NULL)
  43.     {
  44.         root = (struct wezel*)malloc(sizeof *root);
  45.         root->wartosc = n;
  46.         root->ilosc_kluczy=0;
  47.         root->l_syn = NULL;
  48.         root->p_syn = NULL;
  49.         root->rodzic = NULL;
  50.  
  51.     }
  52.     else if(szukaj(root,n)!=NULL)
  53.     {
  54.         struct wezel *tmp = szukaj(root, n);
  55.         tmp->ilosc_kluczy += 1;
  56.         return 0;
  57.     }
  58. //jezeli zadana wartosc jest mniejsza od korzenia idz do lewego poddrzewa
  59.     else if(n < start->wartosc)
  60.     {
  61. //jezeli lewe poddrzewo istnieje wywolaj dla niego ta funkcje rekurencyjnie
  62.     if(start->l_syn != NULL)
  63.     {
  64.         dodawanie(n,start->l_syn);
  65.     }
  66. //jezeli lewe poddrzewo nie istnieje dodaj nowy wezel o zadanej wartosci
  67.     else
  68.     {
  69.     struct wezel *nowy = (struct wezel*)malloc(sizeof *root);
  70.     nowy->wartosc = n;
  71.     nowy->ilosc_kluczy=0;
  72.     nowy->l_syn = NULL;
  73.     nowy->p_syn = NULL;
  74.     nowy->rodzic = start;
  75.     start->l_syn=nowy;
  76.     correct_tree(nowy);
  77.     }
  78.     }
  79. //jezeli zadana wartosc jest wieksza lub rowna korzeniowi idz do prawego poddrzewa
  80.     else
  81.     {
  82. //jezeli prawe poddrzewo istnieje wywolaj dla niego ta funkcje rekurencyjnie
  83.     if(start->p_syn!=NULL)
  84.     {
  85.     dodawanie(n,start->p_syn);
  86.     }
  87. //jezeli prawe poddrzewo nie istnieje dodaj nowy wezel o zadanej wartosci
  88.     else
  89.     {
  90.     struct wezel *nowy = (struct wezel*)malloc(sizeof *root);
  91.     nowy->wartosc = n;
  92.     nowy->ilosc_kluczy=0;
  93.     nowy->l_syn = NULL;
  94.     nowy->p_syn = NULL;
  95.     nowy->rodzic = start;
  96.     start->p_syn=nowy;
  97.     correct_tree(nowy);
  98.     }
  99.     }
  100.     return 0;
  101. }
  102.  
  103. //////////////////////////////////////////////////////////////////
  104.  
  105. void correct_tree(struct wezel *start)
  106. {
  107.     struct wezel *tmp = (struct wezel*)malloc(sizeof *root);
  108.     start->kolor = 'R';
  109.     while((start != root) && (start->rodzic->kolor == 'R'))
  110.     {
  111.         if(start->rodzic == start->rodzic->rodzic->l_syn)
  112.         {
  113.             tmp = start->rodzic->rodzic->p_syn; //za tmp wstawiam wujka start
  114.             if(tmp->kolor == 'R') //przypadek 1
  115.             {
  116.                 start->rodzic->kolor = 'B';
  117.                 tmp->kolor = 'B';
  118.                 start->rodzic->rodzic->kolor='R';
  119.                 start = start->rodzic->rodzic;
  120.                 continue;
  121.             }
  122.             if(start == start->rodzic->p_syn) //przypadek 2
  123.             {
  124.                 start = start->rodzic;
  125.                 rot_L(start);
  126.             }
  127.             start->rodzic->kolor = 'B'; //Przypadek3
  128.             start->rodzic->rodzic->kolor = 'R';
  129.             rot_R(start->rodzic->rodzic);
  130.             break;
  131.         }
  132.         else //Przypadki lustrzane
  133.         {
  134.             tmp = start->rodzic->rodzic->l_syn;
  135.             if(tmp->kolor == 'R') //przypadek 1
  136.             {
  137.                 start->rodzic->kolor = 'B';
  138.                 tmp->kolor = 'B';
  139.                 start->rodzic->rodzic->kolor='R';
  140.                 start = start->rodzic->rodzic;
  141.                 continue;
  142.             }
  143.             if(start == start->rodzic->l_syn) //przypadek 2
  144.             {
  145.                 start = start->rodzic;
  146.                 rot_R(start);
  147.             }
  148.             start->rodzic->kolor = 'B'; //Przypadek3
  149.             start->rodzic->rodzic->kolor = 'R';
  150.             rot_L(start->rodzic->rodzic);
  151.             break;
  152.         }
  153.     }
  154.     root->kolor = 'B';
  155. }
  156.  
  157. //////////////////////////////////////////////////////////////
  158.  
  159. void rot_L(struct wezel *start)
  160. {
  161.     struct wezel *tmp = (struct wezel*)malloc(sizeof *root);
  162.     struct wezel *tmp2 = (struct wezel*)malloc(sizeof *root);
  163.     tmp = start->p_syn;
  164.     if(tmp != NULL)
  165.     {
  166.         tmp2 = start->rodzic;
  167.         start->p_syn = tmp->l_syn;
  168.         if(start->p_syn != NULL)
  169.             start->p_syn->rodzic = start;
  170.         tmp->l_syn = start;
  171.         tmp->rodzic = tmp2;
  172.         start->rodzic = tmp;
  173.         if(tmp2 != NULL)
  174.         {
  175.             if(tmp2->l_syn == start)
  176.                 tmp2->l_syn = tmp;
  177.             else
  178.                 tmp2->p_syn = tmp;
  179.         }
  180.         else root = tmp;
  181.     }
  182.  
  183. }
  184.  
  185. //////////////////////////////////////////////////////////////
  186.  
  187. void rot_R(struct wezel *start)
  188. {
  189.     struct wezel *tmp = (struct wezel*)malloc(sizeof *root);
  190.     struct wezel *tmp2 = (struct wezel*)malloc(sizeof *root);
  191.     tmp = start->l_syn;
  192.     if(tmp != NULL)
  193.     {
  194.         tmp2 = start->rodzic;
  195.         start->l_syn = tmp->p_syn;
  196.         if(start->l_syn != NULL)
  197.             start->l_syn->rodzic = start;
  198.         tmp->p_syn = start;
  199.         tmp->rodzic = tmp2;
  200.         start->rodzic = tmp;
  201.         if(tmp2 != NULL)
  202.         {
  203.             if(tmp2->l_syn == start)
  204.                 tmp2->l_syn = tmp;
  205.             else
  206.                 tmp2->p_syn = tmp;
  207.         }
  208.         else root = tmp;
  209.     }
  210. }
  211.  
  212. ///////////////////////////////////////////////////////////////
  213. //usun wezel start
  214. void kasowanie(struct wezel *start)
  215. {
  216.     if(start == NULL) return;
  217.     if(start->ilosc_kluczy!=0)
  218.     {
  219.         start->ilosc_kluczy--;
  220.         return 0;
  221.     }
  222. //jezeli wezel nie ma dzieci
  223.     if(start->l_syn==NULL && start->p_syn==NULL)
  224.     {
  225. //jezeli wezel jest korzeniem
  226.         if(start->rodzic==NULL)
  227.         {
  228.             root=NULL;
  229.         }
  230. //jezeli wezel jest po lewej stronie rodzica,
  231.         else if(start->rodzic->l_syn==start)
  232.         {
  233. //usun wezel z lewej strony wezla rodzica
  234.             start->rodzic->l_syn=NULL;
  235.         }
  236.         else
  237.         {
  238. //usun wezel z prawej strony wezla rodzica
  239.             start->rodzic->p_syn=NULL;
  240.         }
  241.         //delete start;
  242.     }
  243. //jezeli wezel ma tylko jedno dziecko
  244.     else if(start->l_syn==NULL || start->p_syn==NULL)
  245.     {
  246. //jezeli po lewej stronie nie ma dziecka
  247.     if(start->l_syn==NULL)
  248.     {
  249. //jezeli wezel jest korzeniem
  250.         if(start->rodzic==NULL)
  251.         {
  252.             root=start->p_syn;
  253.         }
  254. //jezeli wezel jest po lewej stronie rodzica
  255.         else if(start->rodzic->l_syn==start)
  256.         {
  257. //przyczep z lewej strony rodzica wezel bedacy po prawej stronie usuwanego wezla
  258.             start->rodzic->l_syn=start->p_syn;
  259.         }
  260.         else
  261.         {
  262. //przyczep z prawej strony rodzica wezel bedacy po prawej stronie usuwanego wezla
  263.             start->rodzic->p_syn=start->p_syn;
  264.         }
  265.     }
  266.     else
  267.     {
  268. //jezeli wezel jest korzeniem
  269.     if(start->rodzic==NULL)
  270.     {
  271.         root=start->l_syn;
  272.     }
  273. //jezeli wezel jest po lewej stronie rodzica
  274.     else if(start->rodzic->l_syn==start)
  275.     {
  276. //przyczep z lewej strony rodzica wezel bedacy po lewej stronie usuwanego wezla
  277.     start->rodzic->l_syn=start->l_syn;
  278.     }
  279.     else
  280.     {
  281. //przyczep z prawej strony rodzica wezel bedacy po prawej stronie usuwanego wezla
  282.         start->rodzic->p_syn=start->l_syn;
  283.     }
  284.     }
  285.     //delete start;
  286.     }
  287.     else
  288.     {
  289. //wstaw w miejsce usuwanego elementu - najmniejsza wartosc z prawego poddrzewa
  290.         struct wezel *temp;
  291.         temp=naj_lewo(start->p_syn);
  292.         start->wartosc = temp->wartosc;
  293.         kasowanie(temp);
  294.     }
  295. }
  296.  
  297. //przejdz drzewo w kolejnosci in order zaczynajac od wezla start
  298. void in_order_tree_walk(struct wezel *start)
  299. {
  300.     if(start->l_syn != NULL) //jezeli ma dzieci po lewej stronie wywolaj funkcje rekurencyjnie
  301.     in_order_tree_walk(start->l_syn);
  302.  
  303.     printf("%d %d\n", start->wartosc, start->ilosc_kluczy); //wypisz wartosc
  304.  
  305.     if(start->p_syn != NULL) //jezeli ma dzieci po prawej stronie wywolaj rekurencyjnie
  306.     in_order_tree_walk(start->p_syn);
  307. }
  308.  
  309. //losuje wartosc w przedziale od a do b
  310. int losowanie(int a, int b)
  311. {
  312.     if(a < b)
  313.         return a + (int)((b-a+1.0)*(rand()/(RAND_MAX+1.0)));
  314.     else
  315.     {
  316.     fprintf(stderr, "złe wartości");
  317.     return -1;
  318.     }
  319. }
  320.  
  321. //przklad uzycia drzewa BST
  322. int main()
  323. {
  324.     int i;
  325.     scanf("%d", &i);
  326. //pobierz rozmiar drzewa z parametru wejsciowego
  327.     int a,k,size=i;
  328.     root = NULL;
  329.  
  330.     struct timezone tz;
  331.     struct timeval tv;
  332.  
  333.     gettimeofday(&tv, &tz);
  334.     srand(tv.tv_usec);
  335.  
  336. //losuj wartosc elementow
  337.     for(i=0;i<size;i++)
  338.     {
  339.         a=losowanie(97,122);
  340.         dodawanie(a, root);
  341.     }
  342.     printf("\n");
  343.  
  344.  
  345. //przejdz drzewo w kolejnosci
  346.     in_order_tree_walk(root);
  347.  
  348. //usun wartosc z drzewa
  349.     printf("Wartość węzła do usunięcia: \n");
  350.     scanf("%d", &k);
  351.     kasowanie(szukaj(root,k));
  352.     printf("\n\n");
  353.  
  354. //przejdz drzewo w kolejnosci
  355.     in_order_tree_walk(root);
  356.  
  357.     return 0;
  358. }
  359.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c: In function ‘dodawanie’:
prog.c:76:5: warning: implicit declaration of function ‘correct_tree’ [-Wimplicit-function-declaration]
     correct_tree(nowy);
     ^~~~~~~~~~~~
prog.c: At top level:
prog.c:105:6: warning: conflicting types for ‘correct_tree’
 void correct_tree(struct wezel *start)
      ^~~~~~~~~~~~
prog.c:76:5: note: previous implicit declaration of ‘correct_tree’ was here
     correct_tree(nowy);
     ^~~~~~~~~~~~
prog.c: In function ‘correct_tree’:
prog.c:125:17: warning: implicit declaration of function ‘rot_L’ [-Wimplicit-function-declaration]
                 rot_L(start);
                 ^~~~~
prog.c:129:13: warning: implicit declaration of function ‘rot_R’ [-Wimplicit-function-declaration]
             rot_R(start->rodzic->rodzic);
             ^~~~~
prog.c: At top level:
prog.c:159:6: warning: conflicting types for ‘rot_L’
 void rot_L(struct wezel *start)
      ^~~~~
prog.c:125:17: note: previous implicit declaration of ‘rot_L’ was here
                 rot_L(start);
                 ^~~~~
prog.c:187:6: warning: conflicting types for ‘rot_R’
 void rot_R(struct wezel *start)
      ^~~~~
prog.c:129:13: note: previous implicit declaration of ‘rot_R’ was here
             rot_R(start->rodzic->rodzic);
             ^~~~~
prog.c: In function ‘kasowanie’:
prog.c:220:16: warning: ‘return’ with a value, in function returning void
         return 0;
                ^
prog.c:214:6: note: declared here
 void kasowanie(struct wezel *start)
      ^~~~~~~~~
prog.c: In function ‘main’:
prog.c:330:21: error: storage size of ‘tz’ isn’t known
     struct timezone tz;
                     ^~
prog.c:330:21: warning: unused variable ‘tz’ [-Wunused-variable]
stdout
copy 
Standard output is empty
https://ideone.com/dGVtqO
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!