Facebook
From Bartek CiesiƄski, 5 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 223
  1. #include "lib.cpp"
  2.  
  3. #include "lib.h"
  4. #include <iostream>
  5. #include <string>
  6. #include <cstdlib>
  7. #include <fstream>
  8. #include <string>
  9.  
  10. using namespace std;
  11.  
  12. struct BST_P{
  13.     int value;
  14.     BST_P *left = nullptr;
  15.     BST_P *right = nullptr;
  16.     BST_P *parent = nullptr;
  17. };
  18.  
  19. void inorder(BST_P *root);
  20. void preorder(BST_P *root);
  21. void postorder(BST_P * root);
  22. BST_P* find(BST_P *root);
  23. BST_P* max(BST_P *root);
  24. BST_P* min(BST_P *root);
  25. BST_P* next(BST_P *root);
  26. BST_P* prev(BST_P *root);
  27. BST_P* insert_BST (BST_P* root, BST_P *x);
  28. void remove_BST (BST_P* root, BST_P *x);
  29.  
  30. struct node
  31. {
  32.     BST_P * wsk;
  33.     node *next;
  34. };
  35.  
  36.  
  37.  
  38. struct Stack
  39. {
  40.     node *top;
  41.     Stack()
  42.      {  
  43.          top = nullptr;
  44.      }
  45.      
  46.      
  47.     void push(BST_P *wezel)
  48.      {
  49.         node * ptr = new node;
  50.         ptr ->wsk = wezel;
  51.         ptr ->next = top;
  52.         top =ptr;
  53.  
  54.      }
  55.      BST_P * pop()
  56.      {
  57.          if(!top) return nullptr;
  58.          node *ptr = top;
  59.          BST_P *x = top->wsk;
  60.          top = top->next;
  61.          delete(ptr);
  62.          return x;
  63.      }
  64.    
  65. };
  66.  
  67.  
  68.  
  69. void inorder(BST_P *root)
  70. {  
  71.     if(!root) return;
  72.     if(root->left)
  73.         inorder(root->left);
  74.     cout << root->value << " ";
  75.     if(root->right)
  76.         inorder(root->right);
  77. }
  78. void postorder(BST_P *root)
  79. {
  80.     if(!root) return;
  81.     if(root ->left)
  82.         postorder(root->left);
  83.     if(root ->right)
  84.         postorder(root -> right);
  85.     cout << root->value;
  86. }
  87. void preorder(BST_P *root)
  88. {
  89.     if(!root) return;
  90.     cout << root ->value;
  91.     if(root ->left)
  92.         preorder(root -> left);
  93.     if(root ->right)
  94.         preorder(root->right);
  95.  
  96. }
  97. BST_P* find(BST_P *root,int x)
  98. {
  99.     if(!root) return nullptr;
  100.     if(root->value==x) return root;
  101.     if(root->value > x) return find(root->left,x);
  102.     else return find(root->right,x);
  103. }
  104. BST_P* min(BST_P *root)
  105. {
  106.     if(!root) return nullptr;
  107.     while(root->left)
  108.     {
  109.         root=root->left;
  110.     }
  111.     return root;
  112. }
  113. BST_P* max(BST_P *root)
  114. {
  115.     if(!root) return nullptr;
  116.     while(root->right)
  117.         root=root->right;
  118.     return root;
  119. }
  120. BST_P* next(BST_P *root)
  121. {
  122.     if(root->right) return min(root->right);
  123.     BST_P* y = root->parent;
  124.     while(y && root->parent)
  125.     {
  126.         root=y;
  127.         y=y->parent;
  128.     }
  129.     return y;
  130. }
  131. BST_P* prev(BST_P *root)
  132. {
  133.     if(root->left) return max(root->left);
  134.     BST_P* y = root->parent;
  135.     while(y&& root->parent)
  136.     {
  137.         root=y;
  138.         y=y->parent;
  139.     }
  140.     return y;
  141. }
  142. BST_P* insert_BST (BST_P* root, BST_P *x)
  143. {
  144.     if(!root){
  145.         root = x;
  146.         return root;
  147.     }
  148.     BST_P *par = nullptr;
  149.     BST_P *son = root;
  150.     while(son)
  151.     {
  152.         par=son;
  153.         if(par->value > x-> value) son = par->left;
  154.         else son = par->right;
  155.     }
  156.     x->parent = par;
  157.     if(par->value > x->value) par->left=x;
  158.     else par->right =x;
  159.     return root;    
  160. }
  161.  
  162. void remove_BST (BST_P* root, BST_P *z)
  163. {
  164.     BST_P* y;
  165.     if(z->left && z->right) y=next(z);
  166.     else y=z;
  167.     BST_P *x;
  168.     if(y->left) x=y->left;
  169.     else x=y->right;
  170.     if(x) x->parent = y->parent;
  171.     if(y->parent)
  172.     {
  173.         if(y=y->parent->left)
  174.         y->parent->left=x;
  175.         else y->parent->right=x;
  176.     }
  177.     else root = x;
  178.     if(z!=y)
  179.     z->value=y->value;
  180.     delete y;
  181.  
  182. }
  183.  
  184. Stack getDataFromFile(Stack s) {
  185.     string token;
  186.     fstream plik;
  187.     int i=0;
  188.  
  189.     plik.open("listaliczb.txt", ios::in);
  190.     if (plik) {
  191.         while (!plik.eof()) {
  192.            getline(plik, token,' ');
  193.            BST_P* t = new BST_P;
  194.            t->value=stoi(token);
  195.             s.push(t);
  196.             cout << s.top->wsk->value << " " ;
  197.  
  198.            
  199.         }
  200.         plik.close();
  201.         return s;
  202.     }
  203.    
  204.     else
  205.     {
  206.         cout << "Nie udalo sie otworzyc pliku OwO" << endl;
  207.     }
  208. }
  209.  
  210.  
  211.  
  212.  
  213. int main()
  214. {
  215.     Stack s;
  216.     s=getDataFromFile(s);
  217.     node* temp = s.top;
  218.  
  219.    
  220.     cout << endl;
  221.     BST_P *root = nullptr;
  222.     while(s.top)
  223.     {
  224.         insert_BST(root,s.pop());
  225.        
  226.     }
  227.     inorder(root);
  228.  
  229.     return 0;
  230. }
  231.