fork(1) download
copy 
  1. #include <iostream>
  2.  
  3. struct wezel
  4. {
  5.     int wartosc;
  6.     struct wezel *rodzic;
  7.     struct wezel *l_syn;
  8.     struct wezel *p_syn;
  9. };
  10. struct wezel *root=NULL;
  11.  
  12. using namespace std;
  13.  
  14. //funkcja zwraca wskaznik elementu o najmniejszej wartosci (najbardziej na lewo)
  15. struct wezel* naj_lewo(struct wezel *start)
  16. {
  17.     if(start && start->l_syn)
  18.         return naj_lewo(start->l_syn);
  19.     else
  20.         return start;
  21. }
  22.  
  23. //funkcja zwraca wskaznik elementu o najwiekszej wartosci (najbardziej na prawo)
  24. struct wezel* naj_prawo(struct wezel *start)
  25. {
  26.     if(start && start->p_syn)
  27.         return naj_prawo(start->p_syn);
  28.     else
  29.         return start;
  30. }
  31.  
  32. //funkcja zwraca wezel o podanej wartosci, badz NULL, gdy taki wezel nie istnieje
  33. struct wezel* szukaj(struct wezel *start, int wartosc)
  34. {
  35.     if(!start)
  36.         return NULL;
  37. //jezeli wezel ma szukana wartosc to odnalezlismy go
  38.     if (start->wartosc == wartosc)
  39.         return start;
  40. //jezeli szukana wartosc jest mniejsza to szukamy w lewym poddrzewie o ile istnieje
  41.     else if (wartosc < start->wartosc && start->l_syn != NULL)
  42.         return szukaj(start->l_syn, wartosc);
  43. //jezeli szukana wartosc jest wieksza to szukamy w prawym poddrzewie o ile istnieje
  44.     else if (wartosc > start->wartosc && start->p_syn != NULL)
  45.         return szukaj(start->p_syn, wartosc);
  46.     return NULL;
  47. }
  48.  
  49. //dodaje wezel o podanej wartosci n, do drzewa o korzeniu start
  50. int dodawanie(int n, struct wezel *start)
  51. {
  52. //jezeli drzewo jest puste to dodaj korzen
  53.     if (root == NULL)
  54.     {
  55.         root = new wezel;
  56.         root->wartosc = n;
  57.         root->l_syn = NULL;
  58.         root->p_syn = NULL;
  59.         root->rodzic = NULL;
  60.     }
  61. //jezeli zadana wartosc jest mniejsza od korzenia idz do lewego poddrzewa
  62.     else if(n < start->wartosc)
  63.     {
  64. //jezeli lewe poddrzewo istnieje wywolaj dla niego ta funkcje rekurencyjnie
  65.         if(start->l_syn != NULL)
  66.         {
  67.             dodawanie(n,start->l_syn);
  68.         }
  69. //jezeli lewe poddrzewo nie istnieje dodaj nowy wezel o zadanej wartosci
  70.         else
  71.         {
  72.             wezel *nowy = new wezel;
  73.             nowy->wartosc = n;
  74.             nowy->l_syn = NULL;
  75.             nowy->p_syn = NULL;
  76.             nowy->rodzic = start;
  77.             start->l_syn=nowy;
  78.         }
  79.     }
  80. //jezeli zadana wartosc jest wieksza lub rowna korzeniowi idz do prawego poddrzewa
  81.     else
  82.     {
  83. //jezeli prawe poddrzewo istnieje wywolaj dla niego ta funkcje rekurencyjnie
  84.         if(start->p_syn!=NULL)
  85.         {
  86.             dodawanie(n,start->p_syn);
  87.         }
  88. //jezeli prawe poddrzewo nie istnieje dodaj nowy wezel o zadanej wartosci
  89.         else
  90.         {
  91.             wezel *nowy = new wezel;
  92.             nowy->wartosc = n;
  93.             nowy->l_syn = NULL;
  94.             nowy->p_syn = NULL;
  95.             nowy->rodzic = start;
  96.             start->p_syn=nowy;
  97.         }
  98.     }
  99.     return 0;
  100. }
  101.  
  102. void kasowanie(struct wezel *start)
  103. {
  104.     if(start==NULL)
  105.         return;
  106. //jezeli wezel nie ma dzieci
  107.     if(start->l_syn==NULL && start->p_syn==NULL)
  108.     {
  109. //jezeli wezel jest korzeniem
  110.         if(start->rodzic==NULL)
  111.         {
  112.             root=NULL;
  113.         }
  114. //jezeli wezel jest po lewej stronie rodzica,
  115.         else if(start->rodzic->l_syn==start)
  116.         {
  117. //usun wezel z lewej strony wezla rodzica
  118.             start->rodzic->l_syn=NULL;
  119.         }
  120.         else
  121.         {
  122. //usun wezel z prawej strony wezla rodzica
  123.             start->rodzic->p_syn=NULL;
  124.         }
  125.         delete start;
  126.     }
  127. //jezeli wezel ma tylko jedno dziecko
  128.     else if((start->l_syn==NULL && start->p_syn!=NULL) || (start->l_syn!=NULL && start->p_syn==NULL))
  129.     {
  130.  
  131. //jezeli po lewej stronie nie ma dziecka
  132.         if(start->l_syn==NULL)
  133.         {
  134. //jezeli wezel jest korzeniem
  135.             if(start->rodzic==NULL)
  136.             {
  137.                 root=start->p_syn;
  138.             }
  139. //jezeli wezel jest po lewej stronie rodzica
  140.             else if(start->rodzic->l_syn==start)
  141.             {
  142. //przyczep z lewej strony rodzica wezel bedacy po prawej stronie usuwanego wezla
  143.                 start->rodzic->l_syn=start->p_syn;
  144.             }
  145.             else
  146.             {
  147. //przyczep z prawej strony rodzica wezel bedacy po prawej stronie usuwanego wezla
  148.                 start->rodzic->p_syn=start->p_syn;
  149.             }
  150.         }
  151.         else
  152.         {
  153. //jezeli wezel jest korzeniem
  154.             if(start->rodzic==NULL)
  155.             {
  156.                 root=start->l_syn;
  157.             }
  158. //jezeli wezel jest po lewej stronie rodzica
  159.             else if(start->rodzic->l_syn==start)
  160.             {
  161. //przyczep z lewej strony rodzica wezel bedacy po lewej stronie usuwanego wezla
  162.                 start->rodzic->l_syn=start->l_syn;
  163.             }
  164.             else
  165.             {
  166. //przyczep z prawej strony rodzica wezel bedacy po prawej stronie usuwanego wezla
  167.                 start->rodzic->p_syn=start->l_syn;
  168.             }
  169.         }
  170.         delete start;
  171.     }
  172.     else
  173.     {
  174. //wstaw w miejsce usuwanego elementu - najmniejsza wartosc z prawego poddrzewa
  175.         struct wezel *temp;
  176.         temp=naj_lewo(start->p_syn);
  177.         start->wartosc = temp->wartosc;
  178.         kasowanie(temp);
  179.     }
  180. }
  181.  
  182. //przejdz drzewo w kolejnosci zaczynajac od wezla start
  183. void in_order_tree_walk(struct wezel *start)
  184. {
  185.     if(start)
  186.     {
  187.         in_order_tree_walk(start->l_syn);
  188.         cout << start->wartosc << " ";
  189.         in_order_tree_walk(start->p_syn);
  190.     }
  191. }
  192.  
  193. void pre_order_tree_walk(struct wezel *start)
  194. {
  195.     if(start)
  196.     {
  197.         cout << start->wartosc << " ";
  198.         pre_order_tree_walk(start->l_syn);
  199.         pre_order_tree_walk(start->p_syn);
  200.     }
  201. }
  202.  
  203. void post_order_tree_walk(struct wezel *start)
  204. {
  205.     if(start)
  206.     {
  207.         post_order_tree_walk(start->l_syn);
  208.         post_order_tree_walk(start->p_syn);
  209.         cout << start->wartosc << " ";
  210.     }
  211. }
  212.  
  213. // Funkcja znajduje następnik węzła p
  214. //-----------------------------------
  215. wezel * znajdzNastepnika(wezel * p)
  216. {
  217.     wezel * r;
  218.  
  219.     if(p)
  220.     {
  221.         if(p->rodzic)
  222.             return naj_lewo(p->p_syn);
  223.         else
  224.         {
  225.             r = p->rodzic;
  226.             while(r && (p == r->p_syn))
  227.             {
  228.                 p = r;
  229.                 r = r->rodzic;
  230.             }
  231.             return r;
  232.         }
  233.     }
  234.     return p;
  235. }
  236.  
  237. // Funkcja znajduje poprzednik węzła p
  238. //------------------------------------
  239. wezel * znajdzPoprzednika(wezel * p)
  240. {
  241.     wezel * r;
  242.  
  243.     if(p)
  244.     {
  245.         if(p->l_syn)
  246.             return naj_prawo(p->l_syn);
  247.         else
  248.         {
  249.             r = p->rodzic;
  250.             while(r && (p == r->l_syn))
  251.             {
  252.                 p = r;
  253.                 r = r->rodzic;
  254.             }
  255.             return r;
  256.         }
  257.     }
  258.     return p;
  259. }
  260.  
  261. void Clear(wezel *x)
  262. {
  263.     if( x != NULL )
  264.     {
  265.         Clear( x->l_syn );
  266.         Clear( x->p_syn );
  267.         delete x;
  268.     }
  269. }
  270.  
  271. int main()
  272. {
  273.     int ileTestow;
  274.     cin >> ileTestow;
  275.  
  276.     for(int i=1; i<=ileTestow; i++)
  277.     {
  278.         cout << "test " << i << endl;
  279.  
  280.         int n;
  281.         cin >> n;
  282.  
  283.         while(n--)
  284.         {
  285.             char command;
  286.             int x;
  287.             cin >> command >> x;
  288.  
  289.             if(command=='I')
  290.             {
  291.                 dodawanie(x,root);
  292.             }
  293.             else if(command=='D')
  294.             {
  295.                 if(root)
  296.                 {
  297.                     wezel *element = szukaj(root,x);
  298.                     if(element)
  299.                     {
  300.                         kasowanie(element);
  301.                     }
  302.                 }
  303.             }
  304.             else if(command=='S')
  305.             {
  306.                 if(root)
  307.                 {
  308.                     wezel *element = szukaj(root,x);
  309.                     if(element)
  310.                     {
  311.                         cout << element->wartosc << endl;
  312.                     }
  313.                     else
  314.                     {
  315.                         cout << "-" << endl;
  316.                     }
  317.                 }
  318.             }
  319.  
  320.             else if(command=='X')
  321.             {
  322.                 if(root)
  323.                 {
  324.                     if(x==0)
  325.                     {
  326.                         wezel *element=naj_lewo(root);
  327.                         cout << element->wartosc << endl;
  328.                     }
  329.                     else if(x==1)
  330.                     {
  331.                         wezel *element=naj_prawo(root);
  332.                         cout << element->wartosc << endl;
  333.                     }
  334.                 }
  335.                 else
  336.                 {
  337.                     cout << "-" << endl;
  338.                 }
  339.             }
  340.  
  341.  
  342.             else if(command=='N')
  343.             {
  344.                 wezel *element=szukaj(root,x);
  345.                 if(element)
  346.                 {
  347.                     wezel *nastepnik = znajdzNastepnika(element);
  348.                     if(nastepnik)
  349.                     {
  350.                         cout << nastepnik->wartosc << endl;
  351.                     }
  352.                     else
  353.                     {
  354.                         cout << "-" << endl;
  355.                     }
  356.                 }
  357.                 else
  358.                 {
  359.                     cout << "-" << endl;
  360.                 }
  361.             }
  362.  
  363.             else if(command=='P')
  364.             {
  365.                 wezel *element=szukaj(root,x);
  366.                 if(element)
  367.                 {
  368.                     wezel *poprzednik = znajdzPoprzednika(element);
  369.                     if(poprzednik)
  370.                     {
  371.                         cout << poprzednik->wartosc << endl;
  372.                     }
  373.                     else
  374.                     {
  375.                         cout << "-" << endl;
  376.                     }
  377.                 }
  378.                 else
  379.                 {
  380.                     cout << "-" << endl;
  381.                 }
  382.             }
  383.  
  384.             else if(command=='R')
  385.             {
  386.                 switch(x)
  387.                 {
  388.                 case 0:
  389.                     in_order_tree_walk(root);
  390.                     break;
  391.                 case 1:
  392.                     pre_order_tree_walk(root);
  393.                     break;
  394.                 case 2:
  395.                     post_order_tree_walk(root);
  396.                     break;
  397.                 }
  398.                 cout << endl;
  399.             }
  400.         }
  401.         Clear(root);
  402.  
  403.         root=NULL;
  404.     }
  405.  
  406.     return 0;
  407. }
  408.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
13
I 5
I 8
I 3
I 4
I 7
R 1
I 1
R 2
S 7
S 6
N 3
D 8
R 0
10
I 4
I 2
R 0
D 2
X 1
X 0
I 1
X 0
X 0
X 1
10
I 4
P 1
I 1
R 1
I 2
I 5
R 0
D 2
I 2
P 1
11
I 3
X 0
I 2
D 3
I 1
I 5
I 4
D 4
I 4
D 4
X 1
stdout
copy 
test 1
5 3 4 8 7 
1 4 3 7 8 5 
7
-
4
1 3 4 5 7 
test 2
2 4 
4
4
1
1
4
test 3
-
4 1 
1 2 4 5 
-
test 4
3
5
https://ideone.com/AeZqYv
language:
C++14 (gcc 8.3)
created:
4 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!