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.  
  8. struct Link //Zveno
  9. {
  10.     int x;//the number we will record
  11.     Link *l, *r;//address fields(left and right)
  12. };
  13.  
  14. Link *Tree=NULL;//pointer whose type is "tree link"
  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
  46. void Add(Link *Node, Link *Branch) //void Push_tree(Zveno *Yz, Zveno *Vetka)
  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. {
  67.     Link *Node = new Link; //Zveno *Yzel=new Zveno;
  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.     {
  82.         NewLink(a[0]); //create node
  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;
  91.         NewLink(a[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.  
  108. //add function to add an element to an array
  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
  117.         temp[number]=newel;  //add new
  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.  
  162. //a function that adds value to the ready tree
  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;
  266.     while(!0) //menu
  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.                     {
  338.                         cout << "Ops...Item not found." << endl;
  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.                 }
  349.             case 5: //Add element
  350.                 {
  351.                     cout << "Enter the item you want to add:" << endl;
  352.                     cin >> addel; //el
  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.                     {
  361.                         AddElement(addel, Tree); //add this item Push_element(el,Tree);
  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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top