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.