SHARE
TWEET

Untitled

a guest Mar 24th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Drzewo bst posortowane
  3. Dodawanie OK
  4. Wypisywanie OK
  5. Sprawdzanie czy drzewo bst
  6. */
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9.  
  10. //typedef struct listek;
  11.  
  12. struct listek {
  13.     int wartosc;
  14.     struct listek* lewy;
  15.     struct listek* prawy;
  16.     //struct listek* tata; 
  17. };
  18. struct drzewo {
  19.     struct listek* szczyt_drzewa;
  20. };
  21. struct listek* konstruktor_listka(int wartosc) {
  22.     struct listek* nowy_lisc;
  23.     nowy_lisc = (struct listek*)malloc(sizeof(struct listek));
  24.     nowy_lisc->wartosc = wartosc;
  25.     nowy_lisc->lewy = NULL;
  26.     nowy_lisc->prawy = NULL;
  27.     //nowy_lisc->tata = NULL;
  28.     return nowy_lisc;
  29. }
  30.  
  31.  
  32. void dodaj_listek(struct drzewo* drzewo, int wartosc) {
  33.     if (drzewo->szczyt_drzewa == NULL) drzewo->szczyt_drzewa = konstruktor_listka(wartosc);
  34.     else {
  35.         int znalazlem_miejsce = 0;
  36.         struct listek* nowy_lisc;
  37.         nowy_lisc = drzewo->szczyt_drzewa;
  38.         while (znalazlem_miejsce == 0) {
  39.             if (wartosc <= nowy_lisc->wartosc) {
  40.                 if (nowy_lisc->lewy == NULL) {
  41.                     nowy_lisc->lewy = konstruktor_listka(wartosc);
  42.                     //nowy_lisc->lewy->tata = nowy_lisc;
  43.                     znalazlem_miejsce = 1;
  44.                 }
  45.                 else nowy_lisc = nowy_lisc->lewy;
  46.             }
  47.             else {
  48.                 if (nowy_lisc->prawy == NULL) {
  49.                     nowy_lisc->prawy = konstruktor_listka(wartosc);
  50.                     //nowy_lisc->prawy->tata = nowy_lisc;
  51.                     znalazlem_miejsce = 1;
  52.                 }
  53.                 else nowy_lisc = nowy_lisc->prawy;
  54.             }
  55.         }
  56.     }
  57. }
  58.  
  59. void wypisz_listek(struct listek* lisc) {
  60.     if (lisc != NULL) {
  61.         wypisz_listek(lisc->lewy);
  62.         printf("%d ", lisc->wartosc);
  63.         wypisz_listek(lisc->prawy);
  64.     }
  65. }
  66. void wypisz_drzewko(struct drzewo* drzewo) {
  67.     wypisz_listek(drzewo->szczyt_drzewa);
  68. }
  69.  
  70. /*
  71. if the node is the left child of its parent,
  72. then it must be smaller than(or equal to)
  73. the parent and it must pass down the value
  74. from its parent to its right subtree to make
  75. sure none of the nodes in that subtree is
  76. greater than the parent
  77.  
  78. if the node is the right child of its parent,
  79. then it must be larger than the parent
  80. and it must pass down the value from its parent
  81. to its left subtree to make sure
  82. none of the nodes in that subtree
  83. is lesser than the parent.
  84. */
  85.  
  86. int czy_bst(struct listek* lisc, int wartosc_min, int wartosc_max) {
  87.     if (lisc == NULL) return 1;
  88.     if (lisc->wartosc < wartosc_min || lisc->wartosc > wartosc_max) return 0;
  89.     if (czy_bst(lisc->lewy, wartosc_min, lisc->wartosc) == 1 &&
  90.         czy_bst(lisc->prawy, lisc->wartosc, wartosc_max) == 1)return 1;
  91.     else return 0;
  92. }
  93. void powiedz_czy_drzewko_jest_bst(struct drzewo* drzewko) {
  94.     if (czy_bst(drzewko->szczyt_drzewa, 0, 1000000)) printf("\ntak, drzewko jest drzewkiem bst");
  95.     else printf("\ndrzeko nie jest bst");
  96. }
  97.  
  98. int main() {   
  99.     struct drzewo klon;
  100.     klon.szczyt_drzewa = NULL;
  101.     dodaj_listek(&klon, 10);
  102.     dodaj_listek(&klon, 5);
  103.     dodaj_listek(&klon, 7);
  104.     dodaj_listek(&klon, 6);
  105.     dodaj_listek(&klon, 2);
  106.     dodaj_listek(&klon, 3);
  107.     dodaj_listek(&klon, 25);
  108.     dodaj_listek(&klon, 5);
  109.     dodaj_listek(&klon, 5);
  110.     dodaj_listek(&klon, 5);
  111.     dodaj_listek(&klon, 33);
  112.     dodaj_listek(&klon, 23);
  113.     dodaj_listek(&klon, 6);
  114.     dodaj_listek(&klon, 1);
  115.     wypisz_drzewko(&klon);
  116.     powiedz_czy_drzewko_jest_bst(&klon);
  117.     return 0;
  118. }
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