SHARE
TWEET

Untitled

a guest Jan 28th, 2020 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct ed
  2. {
  3.     int wartosc;
  4.     struct ed *prawy;
  5.     struct ed *lewy;
  6.     struct ed *rodzic;
  7. };
  8.  
  9. typedef struct ed ed;
  10.  
  11. ed *min(ed *korzen)
  12. {
  13.     if (korzen -> lewy == NULL)
  14.         return korzen;
  15.     else
  16.         korzen = min(korzen->lewy);
  17. }
  18.  
  19. ed *max(ed *korzen)
  20. {
  21.     if (korzen -> prawy == NULL)
  22.         return korzen;
  23.     else
  24.         korzen = max(korzen->prawy);
  25. }
  26.  
  27. ed *dodaj(ed *korzen, int x)
  28. {
  29.     /* If the tree is empty return an empty node */
  30.     if (korzen == NULL)
  31.     {
  32.         ed *q = (ed*)malloc(sizeof(ed));
  33.         q -> wartosc = x;
  34.         q -> lewy = NULL;
  35.         q -> prawy = NULL;
  36.         return q;
  37.     }
  38.  
  39.     /* Otherwise, recur down the tree */
  40.     if (x < korzen->wartosc)
  41.     {
  42.         korzen->lewy = dodaj(korzen->lewy, x);
  43.         korzen->lewy->rodzic = korzen;
  44.     }
  45.  
  46.     else if(x > korzen->wartosc)
  47.     {
  48.         korzen->prawy = dodaj(korzen->prawy, x);
  49.         korzen->prawy->rodzic = korzen;
  50.     }
  51.  
  52.     /* return the (unchanged) node pointer */
  53.     return korzen;
  54. }
  55.  
  56. ed *usun(ed* korzen, int x)
  57. {
  58.     if(korzen == NULL) return korzen;
  59.     if(x < korzen->wartosc)
  60.         korzen->lewy = usun(korzen->lewy, x);
  61.     else if(x > korzen->wartosc)
  62.         korzen->prawy = usun(korzen->prawy, x);
  63.     else
  64.     {
  65.         if(korzen->lewy == NULL)
  66.         {
  67.             ed *tymczasowy = korzen->prawy;
  68.             free(korzen);
  69.             return tymczasowy;
  70.         }
  71.         else if(korzen->prawy == NULL)
  72.         {
  73.             ed *tymczasowy = korzen->lewy;
  74.             free(korzen);
  75.             return tymczasowy;
  76.         }
  77.          ed *tymczasowy = min(korzen->prawy);
  78.          korzen->wartosc = tymczasowy->wartosc;
  79.          korzen->prawy = usun(korzen->prawy, tymczasowy->wartosc);
  80.     }
  81.     return korzen;
  82. }
  83.  
  84. ed *szukaj(ed *korzen, int x)
  85. {
  86.     if(korzen == NULL || korzen->wartosc == x)
  87.         return korzen;
  88.     if(korzen->wartosc < x)
  89.         return szukaj(korzen->prawy, x);
  90.     return szukaj(korzen->lewy, x);
  91. }
  92.  
  93. void drukuj(ed *korzen, int spacje)
  94. {
  95.     if(korzen == NULL)
  96.         return;
  97.     int i;
  98.     spacje += 10;
  99.     drukuj(korzen->prawy, spacje);
  100.     printf("\n");
  101.     for(i=10; i<spacje; i++)
  102.         printf(" ");
  103.     printf("%d\n", korzen->wartosc);
  104.     drukuj(korzen->lewy, spacje);
  105. }
  106.  
  107. ed *poprzednik(ed *korzen)
  108. {
  109.     if(korzen->lewy)
  110.         return max(korzen->lewy);
  111.     else
  112.     {
  113.         while(korzen->rodzic && (korzen->rodzic->lewy == korzen))
  114.             korzen = korzen->rodzic;
  115.     }
  116.     return korzen->rodzic;
  117. }
  118.  
  119. ed *nastepnik(ed *korzen)
  120. {
  121.     if(korzen->prawy)
  122.         return max(korzen->prawy);
  123.     else
  124.     {
  125.         while(korzen->rodzic && (korzen->rodzic->prawy == korzen))
  126.             korzen = korzen->rodzic;
  127.     }
  128.     return korzen->rodzic;
  129. }
  130.  
  131. int ile_x(ed *korzen, int x) // zlicza liczbe x-ów w drzewie
  132. {
  133.     if(korzen == 0)
  134.         return 0;
  135.     int pom = 0;
  136.     if(korzen->wartosc == x)
  137.         pom = 1;
  138.     return ile_x(korzen->lewy, x) + ile_x(korzen->prawy, x) + pom;
  139. }
  140.  
  141. bool czy_te_same(ed *korzen_1, ed *korzen_2)
  142. {
  143.     if(korzen_1 == 0) // a¿ skoñczymy sprawdzaæ wartoœci 1 drzewa w 2 drzewie
  144.         return true;
  145.     if(ile_x(korzen_2, korzen_1->wartosc) > 0) // przeszukuje w drzewie nr 2 wartosci z 1 drzewa
  146.         return czy_te_same(korzen_1->lewy, korzen_2) && czy_te_same(korzen_1->prawy, korzen_2);
  147.     else
  148.         return false;
  149. }
  150.  
  151. int liczba_lisci(ed *korzen)
  152. {
  153.     if(korzen == NULL)
  154.         return 0;
  155.     if(korzen->lewy == NULL && korzen->prawy == NULL)
  156.         return 1;
  157.     else
  158.         return liczba_lisci(korzen->lewy) + liczba_lisci(korzen->prawy);
  159. }
  160.  
  161. void sumaLisci(ed *korzen, int *suma)
  162. {
  163.     if(korzen != NULL)
  164.         return;
  165.     if(korzen->lewy != NULL && korzen->prawy != NULL)
  166.         *suma += korzen->wartosc;
  167.     sumaLisci(korzen->lewy, suma);
  168.     sumaLisci(korzen->prawy, suma);
  169. }
  170.  
  171. int glebokosc(ed *korzen)
  172. {
  173.     if(korzen == NULL)
  174.         return 0;
  175.     else
  176.     {
  177.         int glebokoscL = glebokosc(korzen->lewy);
  178.         int glebokoscR = glebokosc(korzen->prawy);
  179.         if(glebokoscL > glebokoscR)
  180.             return(glebokoscL + 1);
  181.         else return(glebokoscR + 1);
  182.     }
  183. }
  184.  
  185. int liczebnosc(ed *korzen)
  186. {
  187.     if(korzen == NULL)
  188.         return 0;
  189.     else
  190.         return(liczebnosc(korzen->lewy) + liczebnosc(korzen->prawy) + 1);
  191. }
  192.  
  193. int liczebnosc(wsk T)
  194. {
  195.     if(T == NULL)
  196.         return 0;
  197.     else
  198.         return(liczebnosc(T->lewy) + liczebnosc(T->prawy) + 1);
  199. }
  200.  
  201. int wywazenie(wsk T) // roznica pomiedzy liczebnosciami lewego i prawego poddrzewa
  202. {
  203.     if(T == NULL)
  204.         return 0;
  205.     else
  206.         return max(abs(liczebnosc(korzen->lewy) - liczebnosc(korzen->prawy)), wywazenie(korzen->lewy), wywazenie(korzen->prawy));
  207. }
  208.  
  209. int wywazenie(wsk T) // roznica pomiedzy wysokosciami lewego i prawego poddrzewa
  210. {
  211.     if(T == NULL)
  212.         return 0;
  213.     else
  214.         return max(abs(glebokosc(korzen->lewy) - glebokosc(korzen->prawy)), wywazenie(korzen->lewy), wywazenie(korzen->prawy));
  215. }
  216.  
  217. int maxSzerokosc(ed *korzen)
  218. {
  219.     int maxSzer = 0;
  220.     int szer;
  221.     int w = glebokosc(korzen);
  222.     int i;
  223.     for(i=1; i<=w; i++)
  224.     {
  225.         szer = pobSzerokosc(korzen, i);
  226.         if(szer > maxSzer)
  227.             maxSzer = szer;
  228.     }
  229.     return maxSzer;
  230. }
  231.  
  232. int pobSzerokosc(ed *korzen, int poziom)
  233. {
  234.     if(korzen == NULL)
  235.         return 0;
  236.     if(poziom == 1)
  237.         return 1;
  238.     else if(poziom > 1)
  239.         return pobSzerokosc(korzen->lewy, poziom - 1) + pobSzerokosc(korzen->prawy, poziom - 1);
  240. }
  241.  
  242. void lustrzane_odbicie(ed *korzen)
  243. {
  244.     if(korzen == NULL)
  245.         return;
  246.     else
  247.     {
  248.         ed *tymczasowy;
  249.         lustrzane_odbicie(korzen->lewy);
  250.         lustrzane_odbicie(korzen->prawy);
  251.         tymczasowy = korzen->lewy;
  252.         korzen->lewy = korzen->prawy;
  253.         korzen->prawy = tymczasowy;
  254.     }
  255. }
  256.  
  257. int CzySaIdentyczne(ed *a, ed *b)
  258. {
  259.     if(a == NULL & b == NULL)
  260.         return 1;
  261.     if(a != NULL && b!= NULL)
  262.     {
  263.         return (a->wartosc == b->wartosc && CzySaIdentyczne(a->lewy, b->lewy) && CzySaIdentyczne(a->prawy, b->prawy));
  264.     }
  265.     return 0; // jesli jedno jest puste a drugie nie
  266. }
  267.  
  268. int CzySaOdbiciemLustrzanym(ed *a, ed *b)
  269. {
  270.     if(a == NULL && b == NULL)
  271.         return true;
  272.     if(a == NULL || b == NULL)
  273.         return false;
  274.     return a->wartosc == b->wartosc && CzySaOdbiciemLustrzanym(a->lewy, b->prawy) && CzySaOdbiciemLustrzanym(a->prawy, b->lewy);
  275. }
  276.  
  277. void drukLevel(ed *korzen)
  278. {
  279.     int w = glebokosc(korzen);
  280.     int i;
  281.     for(i=1; i<=w; i++)
  282.     {
  283.         drukujDanyLevel(korzen, i);
  284.         printf("\n");
  285.     }
  286. }
  287.  
  288. void drukujDanyLevel(ed *korzen, int level)
  289. {
  290.     if(korzen == NULL)
  291.         return;
  292.     if(level == 1)
  293.         printf("%d ", korzen->wartosc);
  294.     else if(level > 1)
  295.     {
  296.         drukujDanyLevel(korzen->lewy, level - 1);
  297.         drukujDanyLevel(korzen->prawy, level - 1);
  298.     }
  299. }
  300.  
  301. DFS
  302.  
  303. Mam listê s¹siadów, listê odwiedzonych oraz stos. Zaczynam w A. S¹siedzi A: B i S. Dodajê A do odwiedzonych oraz do stosu (na samym dole). Odwiedzam nieodwiedzonych s¹siadów tego elementu,
  304. który jest na górze stosu (A). Nieodwiedzeni s¹siedzi: B i S. Dodajê B na górê stosu i do listy odwiedzonych. S¹siedzi B: brak. Nieodwiedzeni s¹siedzi B: brak. Usuwam B ze stosu. A jest
  305. znowu na górze stosu. Nieodwiedzeni s¹siedzi A: S. Dodajê S na górê stosu i do listy odwiedzonych. S¹siedzi S: A, C i G. Nieodwiedzeni s¹siedzi S: C i G. Dodajê C na górê stosu i do listy odwiedzonych.
  306. Itd...
  307. /*Rysowanie: idziemy od pierwszego elementu w dó³, a¿ dojdziemy do elementu, który nie ma jako s¹siada nastêpnego elementu z odwiedzonych. Wtedy wracamy do góry, do pierwszego z kolei elementu,
  308. który ma jako s¹siada nastêpny element z odwiedzonych. Wtedy tworzy siê rozwidlenie.*/
  309. *********************************************************************************************************************************************************************************************
  310.  
  311. BFS
  312.  
  313. Mam listê s¹siadów, listê odwiedzonych oraz kolejkê. Zaczynam w A. Dodajê A do odwiedzonych. Pracujê na A. S¹siedzi A: B i S. Dodajê B i S do kolejki (od góry do do³u) oraz do listy odwiedzonych.
  314. Teraz pracujê na pierwszym elemencie kolejki: B. Zdejmujê B z kolejki. S¹siedzi B: A. A ju¿ by³o odwiedzone. Teraz pracujê na S. Zdejmujê S z kolejki. S¹siedzi S: A, C i G. Nieodwiedzeni
  315. s¹siedzi S: C i G. Dodajê C i G do kolejki i do listy odwiedzonych. Teraz pracujê na C. Zdejmujê C z kolejki. S¹siedzi C: D, E, F i S. Nieodwiedzeni s¹siedzi C: D, E i F. Dodajê D, E i F
  316. do kolejki (pod G) i do listy odwiedzonych. Teraz pracujê na G... itd.
  317. /*Rysowanie: idziemy od pierwszego elementu i w drugiej linii dodajemy tyle elementów, ile on ma s¹siadów. Nastêpnie tak samo.*/
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