SHARE
TWEET

tree

a guest May 19th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <ctime>
  3. #include <memory>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. struct BSTnode {                     //liść
  9.  
  10.     int wartosc;                    //wartość
  11.     unique_ptr<BSTnode> lewo;       //odnośnik w lewo
  12.     unique_ptr<BSTnode> prawo;      //odnośnik w prawo
  13.  
  14.     BSTnode(int a) {
  15.  
  16.         this->wartosc = a;
  17.         this->lewo = nullptr;
  18.         this->prawo = nullptr;
  19.  
  20.     }
  21. };
  22.  
  23. // wypisywanie drzewa na ekran
  24. ostream& operator << (ostream& stream, BSTnode* bst) {
  25.     if (bst) {
  26.         stream << bst->lewo.get() << bst->wartosc << bst->prawo.get();
  27.     }
  28.     else return stream << " ";
  29. }
  30.  
  31. // in-order
  32. void inorder(BSTnode *bst) {
  33.     cout << "in-orer: " << bst->lewo.get() << bst->wartosc << bst->prawo.get() << endl;
  34. }
  35.  
  36. // pre-order
  37. void preorder(BSTnode *bst) {
  38.     cout << "pre-order: " << bst->wartosc << bst->lewo.get() << bst->prawo.get() << endl;
  39. }
  40.  
  41. //past-order
  42. void postorder(BSTnode *bst) {
  43.     cout << "post-order: " << bst->lewo.get() << bst->prawo.get() << bst->wartosc << endl;
  44. }
  45.  
  46. // dodawanie elementu do drzewa
  47. void addtotree(unique_ptr<BSTnode>& root, int a) {
  48.    
  49.     if (root) {
  50.         if (root->wartosc > a && root->wartosc != a) addtotree(root->lewo, a);
  51.         if (root->wartosc < a && root->wartosc != a) addtotree(root->prawo, a);
  52.     }
  53.     else root = make_unique<BSTnode>(a);
  54. }
  55.  
  56. // szukanie minimalnej wartosci w drzewie
  57. int min(BSTnode* b) {
  58.    
  59.     if (b) {
  60.         if (b->lewo) {
  61.             return min(b->lewo.get());
  62.         }
  63.         else return b->wartosc;
  64.     }
  65. }
  66.  
  67. // szuaknie elementu w drzewie
  68. bool szukajka(BSTnode* b, const int& c) {
  69.    
  70.     if (b)
  71.     {
  72.         if (b->wartosc == c) return 1;
  73.         else if (b->wartosc < c) szukajka(b->prawo.get(), c);
  74.         else if (b->wartosc > c) szukajka(b->lewo.get(), c);
  75.     }
  76.     else return 0;
  77. }
  78.  
  79. // zapisywanie drzewa do wektora
  80. void saveToVector(unique_ptr<BSTnode>& tree, vector<int>& vector)
  81. {
  82.     if (tree)
  83.     {
  84.         vector.push_back(tree->wartosc);
  85.         saveToVector(tree->lewo, vector);
  86.         saveToVector(tree->prawo, vector);
  87.     }
  88. }
  89.  
  90. // usuwanie wybranego elementu z drzewa
  91. void remove(unique_ptr<BSTnode>& tree, const int& value)
  92. {
  93.     vector<int> tmp;
  94.     saveToVector(tree, tmp);
  95.     tree = nullptr;
  96.     for (int i = 0; i < tmp.size(); i++)
  97.     {
  98.         if (tmp[i] != value) addtotree(tree, tmp[i]);
  99.     }
  100. }
  101.  
  102. int main() {
  103.  
  104.     srand(time(NULL));
  105.  
  106.     // tworzenie drzewa o korzeniu 5
  107.     unique_ptr<BSTnode> b = make_unique<BSTnode>(5);
  108.  
  109.     //dodawanie losowych 10 elementow
  110.     for (int i = 0; i < 10; i++) {
  111.         addtotree(b, rand() % 10 + 1);
  112.     }
  113.  
  114.     // wyświetlanie drzewa w roznych opcjach przejsc
  115.     inorder(b.get());
  116.     preorder(b.get());
  117.     postorder(b.get());
  118.    
  119.     //szukanie minimalnej wartosci podanej przez urzytkownika
  120.     cout << "wartosc minimalna: " << min(b.get()) << endl;
  121.     int x;
  122.     cout << "wprowadz liczbe szukana: ";
  123.     cin >> x;
  124.     cin.clear();
  125.     cin.ignore(1000, '\n');
  126.     // sprawdzenie czy element podany przez uzytkownika istnieje
  127.     cout << "czy element " << x << " istnieje? " << szukajka(b.get(), x) << endl;
  128.    
  129.    
  130.     //usuwanie z drzewa elementu podanego przez uzytkownika
  131.     int y;
  132.     cout << "podaj cyfre ktora chesz ususnac z drzewa: ";
  133.     cin >> y;
  134.     cin.clear();
  135.     cin.ignore(1000, '\n');
  136.     remove(b, y);
  137.     cout << endl << b.get();
  138.  
  139.     cin.get();
  140.     return 0;
  141. }
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