• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jun 19th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <ctime>
3. #include <cstdlib>
4. #include <ctime>
5.
6. using namespace std;
7.
9. {
10.     int x;//the number we will record
12. };
13.
15.
16. //The sort function of the array
17. void Sort(int *a, int n){ //void QuickSort(int *a, int n)
18.     int left=0;
19.     int right=n-1;
20.     int middle=a[n/2];
21.     while(left<=right)
22.     {
23.         while(a[left]<middle)
24.         {
25.             left++;//move the pointer to the right until it approaches the middle element
26.         }
27.         while(a[right]>middle)
28.         {
29.             right--;
30.         }
31.         if(left<=right)
32.         {
33.             swap(a[left], a[right]);//change the items in places
34.             left++;
35.             right--;
36.         }
37.     }
38.     if (right>0)
39.        Sort(a, right+1);
40.
41.     if (left < n-1)
42.        Sort(a+left, n-left);
43. }
44.
45. //a function that adds value to the tree
47. {
48.     //work with the left part of the tree
49.     if(Node->x<=Branch->x) //condition: the entered element is smaller than the node
50.     {
51.         if(Branch->l) //condition: there is a left tree
52.         Add(Node,Branch->l); //recursively write the element to the left in the free space
53.         else
54.         Branch->l=Node; //otherwise, the left subtree becomes a node
55.     }
56.     else //else a free site is not
57.     {
58.       if(Branch->r) //condition: there is a right tree
59.         Add(Node,Branch->r); //recursively write the element to the right in the free space
60.       else Branch->r=Node;//otherwise, the right subtree becomes a node
61.     }
62. }
63.
64. //parent and 2 child creation function
65. void NewLink(int x) //void NewZveno(int x)
66. {
68.     Node->x = x; //write data to our node
69.     Node->l = NULL; //create the left link and initialize to avoid errors
70.     Node->r = NULL; //create the left link and initialize
71.     if(Tree)
72.     {
73.         Add(Node, Tree); //call the add function from Node if there is a tree
74.     }else Tree = Node; //put in the base of out node if there is not a tree
75. }
76.
77. //Tree building function
78. void BuildTree(int *a, int n){ //void Mass(int *a, int n)
79.     int middle=0; //this is a variable for the middle element
80.     if(n==1)
81.     {
83.     }else if(n==2)
84.     {
85.         middle = n/2; //calculate middle element
86.         NewLink(a[n/2]); //make it a node
87.         BuildTree(a,1); //recursively arrange other elements
88.     }else
89.     {
90.         middle = n/2;
92.         BuildTree(a, n/2); //recursively work with the left part or the array; build the left subtree
93.         BuildTree(a+n/2+1, n-n/2-1); //recursively work with the right part or the array; build the right subtree
94.     }
95. }
96. //a function that counts the number of nodes in the tree
97. int LengthTree(Link *Derevo) //int Dlina_Tree(Zveno *Derevo)
98. {
99.     if(Derevo==NULL) //if there is no tree
100.     {
101.         return (0);
102.     }else
103.     {
104.         return(LengthTree(Derevo->l)+1+LengthTree(Derevo->r)); //count and return the number of nodes
105.     }
106. }
107.
109. int *AddElToArray (int *olditem, int number, int newel) //int *NewM(int *staryi, int kolich, int e)
110. {
111.     int numberTemp=number+1; // create a variable for more elements;
112.     int *temp = new int[numberTemp]; //create an array with a large number of elements;
113.
114.     if(number==1)
115.     {
116.         temp[0]=olditem[0]; // shift the array element
118.     }else
119.     {
120.         for(int i=0; i<number; i++)
121.         {
122.             temp[i] = olditem[i]; //shift the array elements
123.         }
124.         temp[number] = newel; // in the last place put element that you want to add
125.         return temp; //return new array
126.     }
127.     return temp;
128. }
129.
130. //Writing a tree to an array
131. void WritingTreeToAnArray (int *arr, int b, Link *MR) // MassisDer(ARR, m, T);
132. {
133.     if(b==1)
134.     {
135.         arr[0]=MR->x; //writing a single element to the array
136.     }else if(b==2)
137.     {
138.         arr[b/2]=MR->x; //write the node as the middle element of the array
139.         WritingTreeToAnArray(arr, 1, MR->l); //recursively insert the last element into the array
140.     }else
141.     {
142.         arr[b/2]=MR->x; //write the node as the middle element
143.         WritingTreeToAnArray(arr, b/2, MR->l); // recursively write the left subtree to the left part of the array
144.         WritingTreeToAnArray(arr+b/2+1, b-b/2-1, MR->r); //recursively write the right subtree to the right part of the array
145.     }
146. }
147.
148.
149.
150. //tree delete function
151. void DeleteTree(Link *Emptily) //void Delete_Tree(Zveno *Pysto)
152. {
153.     if(Emptily)
154.     {
155.         if(Emptily->l)DeleteTree(Emptily->l); //recursively remove left part
156.         if(Emptily->r)DeleteTree(Emptily->r); //recursively remove right part
157.         delete Emptily; //remove last item
158.         Emptily==NULL;
159.     }
160. }
161.
163. void AddElement (int element, Link *T) //void Push_element(int element, Zveno *T)
164. {
165.     int m=0;//create a variable
166.     m=LengthTree(T);//assign the number of nodes in the tree to the element
167.     int *ARR=new int[m];//create new array with the number of elements equal number of node in the tree
168.     WritingTreeToAnArray(ARR, m, T); //write the tree to the new array
169.     int g = m + 1; //create a variable with the number of elements 1 more
170.     int *p = new int[g]; //create new array with the number of elements 1 more
171.     p = AddElToArray(ARR, m, element); //add a new item to array
172.     Sort(p, g); //sort array
173.     DeleteTree(Tree); //delete old tree
174.     Tree = NULL;
175.     BuildTree(p, g);
176. }
177.
178. //remove element from array
179. int *RemElFromArr( int *old, int num, int E) //int *NeM(int *star, int kol, int E)
180. {
181.     int p = 0;
182.     int b = 0;
183.     int numTemp = num-1; //create a variable with a smaller of items 1
184.     int *Temp = new int[numTemp]; //create new array with a smaller of items 1
185.
186.     for(int i = 0; i < num; i++)
187.     {
188.         if(old[i]!= E || p==1) //conditions: elements of the array is not equal to that which is necessary to remove or token =1
189.         {
190.             Temp[b] = old[i]; // shift the array elements
191.             b++;
192.         }
193.         else
194.         {
195.             p = 1;
196.         }
197.     }
198.     if (p == 0) return NULL;
199.
200.     return Temp;
201.
202. }
203.
204. //function of removing an element from the tree
205. int RemoveElement(int element, Link *RM) //int Delete_element(int elem, Zveno *YY)
206. {
207.     int k = LengthTree(RM); //put in a new variable the number of nodes in the tree
208.     int N[k]; //create new array with this number of elements
209.     WritingTreeToAnArray(N, k, RM); //shift tree to a new array
210.     int s = k -1; //create a variable with a smaller of items 1
211.     int *L = new int[s]; //create array with this number elements
212.
213.     if(!L) return 0;
214.
215.     L = RemElFromArr(N, k, element); //remove an element from the array
216.     Sort(L, s);
217.     DeleteTree(Tree); //remove old tree
218.     Tree = NULL;
219.     BuildTree(L, s);
220. }
221.
222. //tree print function
223. void PrintTree(Link *PR) //void Print_Tree(Zveno *Vidno)
224. {
225.     if(PR)
226.     {
227.         cout << "Node: " << PR->x; //print Node
228.         if(PR->l) cout << " Left subtree: " << PR->l->x;
229.         if(PR->r) cout << " Right subtree: " << PR->r->x;
230.         cout << endl;
231.
232.         PrintTree(PR->l); //recursively print left subtree
233.         PrintTree(PR->r); //recursively print right subtree
234.     }
235. }
236.
237. //the search function for an element in the tree
238. int SearchElement(int item, Link *Tr) //int Search_element(int item, Zveno *Tr)
239. {
240.     if(item<Tr->x)//condition: the sought element is smaller than the vertex
241.    {
242.        if(Tr->l)//condition: there is a left subtree
243.        SearchElement(item, Tr->l);//recursively looking for item the left subtree
244.        else return 0;//else nothing return
245.    }else if(item>Tr->x)//condition: the sought element is bigger than the vertex
246.    {
247.        if(Tr->r)//condition: there is a right subtree
248.         SearchElement(item,Tr->r);//recursively looking for item the right subtree
249.         else return 0;
250.    }else //item equal the vertex
251.    {
252.        return item;
253.    }
254. }
255.
256. int main()
257. {
258.     cout << " Hello! This program creates a perfectly balanced search tree (PBST) from a given array " << endl;
259.     int choice; //variable that indicates the selected action
260.     int n; //number of array elements
261.     int addel; // the item that the user wants to add
262.     int rm; // the item that the user wants to remove
263.     int findel; // the item that the user wants to find
264.     time_t seconds;
265.     time_t seconds1;
267.     {
268.         cout << " Please select action: " << endl;
269.         cout << " 1 - Set an array and make an array of the PBST" << endl;
270.         cout << " 2 - Display PBST" << endl;
271.         cout << " 3 - Remove item from PBST" << endl;
272.         cout << " 4 - Remove entire PBST" << endl;
273.         cout << " 5 - Add item to PBST" << endl;
274.         cout << " 6 - Find element in PBST" << endl;
275.         cout << " 0 - EXIT" << endl;
276.         cin >> choice;
277.         switch(choice)
278.         {
279.             case 0://Exit
280.                 {
281.                     cout << "Exit in progress..." << endl;
282.                     return 0;
283.                     break;
284.                 }
285.
286.             case 1: //Make tree
287.                 {
288.                     cout << "Enter the number of elements in the array: " << endl;
289.                     cin >> n;
290.                     int *a = new int[n];
291.                     cout << "Enter array elements (elements need not be repeated): " << endl;
292.                     for(int i = 0; i < n; i++) //set an array
293.                     {
294.                        // cin >> a[i];
295.                         a[i] = rand();
296.                     }
297.                     cout << "Your array is: " << endl;
298.                     for(int i = 0; i < n; i++)
299.                     {
300.                         cout << a[i] << " ";
301.                     }
302.                     cout << endl;
303.                     seconds = time (NULL);
304.                     cout << seconds << endl;
305.                     Sort(a,n); //sort array  QuickSort(a,n);
306.
307.                     BuildTree(a,n); //build PBST  Mass(a,n);
308.                     seconds1 = time (NULL);
309.                     cout << seconds1 << endl;
310.                     cout << "PBST was made" << endl;
311.                     cout << endl;
312.                     break;
313.                 }
314.
315.             case 2: //display tree
316.                 {
317.                     if(Tree)
318.                     {
319.                         PrintTree(Tree);//if the tree is print it Print_Tree(Tree);
320.                     }else
321.                     {
322.                         cout << "No tree" << endl;
323.                     }
324.                     break;
325.                 }
326.
327.             case 3: //remove item
328.                 {
329.                     cout << "Enter the item you want to delete: " << endl;
330.                     cin >> rm; //eml
331.                     int v = SearchElement(rm, Tree); //check the element for presence in the tree Search_element(eml, Tree);
332.                     if(v)
333.                     {
334.                         cout << "The element is deleted." << endl;
335.                         RemoveElement(rm, Tree); //remove element Delete_element(eml, Tree);
336.                     }else
337.                     {
339.                     }
340.                     break;
341.                 }
342.             case 4: //remove tree
343.                 {
344.                     DeleteTree(Tree); //remove tree Delete_Tree(Tree);
345.                     Tree = NULL; //initialize the tree with zero
346.                     cout << " Tree removed." << endl;
347.                     break;
348.                 }
350.                 {
351.                     cout << "Enter the item you want to add:" << endl;
353.                     int k; //int r; создаем элемент
354.                     k = SearchElement(addel, Tree); //check the element for uniqueness Search_element(el, Tree);
355.                     if(k)
356.                     {
357.                         cout << "This element is already in the tree" << endl;
358.
359.                     }else
360.                     {
362.                         cout << "Item added! " << endl;
363.                         cout << endl;
364.                     }
365.                     break;
366.                 }
367.
368.             case 6: //find element in the tree
369.                 {
370.                     cout << "Enter the item you want to find: " << endl;
371.                     cin >> findel; //h
372.                     int w;
373.                     w = SearchElement(findel, Tree); //find item
374.                     if(w)
375.                     {
376.                         cout << "This element is in the tree. " << endl;
377.                     }else
378.                     {
379.                         cout << "This element didn't find. " << endl;
380.                     }
381.                 }
382.         }
383.     }
384. }
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.
Not a member of Pastebin yet?