Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Apr 3rd, 2020 152 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stack>
  3. #include <ctime>
  4.  
  5. using namespace std;
  6.  
  7. class Node{
  8. public:
  9.     Node(int);
  10.     int key;
  11.     Node* leftChild;
  12.     Node* rightChild;
  13.     char charArray[10];
  14. };
  15.  
  16. Node::Node(int k){
  17.     this->key = k;
  18.     this->rightChild = nullptr;
  19.     this->leftChild = nullptr;
  20.     string keyString = to_string(k);
  21.     int keyLength = keyString.length();
  22.     for (int i=0;i<keyLength;i++){
  23.         this->charArray[i] = keyString[i];
  24.     }
  25. }
  26.  
  27. class BinarySearchTree{
  28.     int countScanPreorder(Node*);
  29.     int countScanInorder(Node*);
  30.     int countScanPostorder(Node*);
  31.  
  32. public:
  33.     Node* root;
  34.     BinarySearchTree();
  35.     bool InsertNode(int);
  36.     void InsertNodesBulk(int);
  37.     Node* FindNode(int);
  38.     bool RemoveNode(int);
  39.     void scanPreorder(Node*);
  40.     void scanInorder(Node*);
  41.     void scanPostorder(Node*);
  42. };
  43.  
  44. int BinarySearchTree::countScanPreorder(Node* current) {
  45.     int counter = 1;
  46.     if(current== nullptr){
  47.         return 0;
  48.     }
  49.     if(current!= nullptr){
  50.         cout << current->key << " ";
  51.         counter += countScanPreorder(current->leftChild);
  52.         counter += countScanPreorder(current->rightChild);
  53.  
  54.     }
  55.     return counter;
  56. }
  57.  
  58. void BinarySearchTree::scanPreorder(Node* current){
  59.     int c = countScanPreorder(current);
  60.     cout << c;
  61. }
  62.  
  63. int BinarySearchTree::countScanInorder(Node* current) {
  64.     int counter = 1;
  65.     if(current== nullptr){
  66.         return 0;
  67.     }
  68.     if(current!= nullptr){
  69.         cout << current->key << " ";
  70.         counter += countScanInorder(current->leftChild);
  71.         counter += countScanInorder(current->rightChild);
  72.  
  73.     }
  74.     return counter;
  75. }
  76.  
  77.  
  78. void BinarySearchTree::scanInorder(Node* current){
  79.     int c = countScanInorder(current);
  80.     cout << c;
  81. };
  82.  
  83. int BinarySearchTree::countScanPostorder(Node* current) {
  84.     int counter = 1;
  85.     if(current== nullptr){
  86.         return 0;
  87.     }
  88.     if(current!= nullptr){
  89.         cout << current->key << " ";
  90.         counter += countScanPostorder(current->leftChild);
  91.         counter += countScanPostorder(current->rightChild);
  92.     }
  93.     return counter;
  94. }
  95. void BinarySearchTree::scanPostorder(Node* current){
  96.     int c = countScanPostorder(current);
  97.     cout << c;
  98. }
  99.  
  100. bool BinarySearchTree::RemoveNode(int k){
  101.     Node* current = this->root;
  102.     if(current == nullptr){
  103.         return false;
  104.     }
  105.     stack<Node*> nodesStack;
  106.  
  107.     nodesStack.push(current);
  108.     while((current!=nullptr && current->key!=k)){
  109.         if(current->key < k){
  110.                 current = current->rightChild;
  111.                 }
  112.             else{
  113.                 current = current->leftChild;
  114.         }
  115.         nodesStack.push(current);
  116.     }
  117.  
  118.     if(current == nullptr){
  119.         return false;
  120.     }
  121.     current = nodesStack.top();
  122.  
  123.     //wezel jest lisciem
  124.     if(current->leftChild == nullptr && current->rightChild == nullptr){
  125.         nodesStack.pop();
  126.         Node* parent = nodesStack.top();
  127.         if(parent->leftChild == current){
  128.             parent->leftChild = nullptr;
  129.         }else{
  130.             parent->rightChild = nullptr;
  131.         }
  132.         delete current;
  133.     }
  134.     //wezel ma dwoch potomkow
  135.     else if(current->leftChild != nullptr && current->rightChild != nullptr){
  136.         Node* nodeToRemove = current;
  137.         current = current->rightChild;
  138.         nodesStack.push(current);
  139.         while(current->leftChild != nullptr){
  140.             current = current->leftChild;
  141.             nodesStack.push(current);
  142.         }
  143.         Node* successor = nodesStack.top();
  144.         nodesStack.pop();
  145.         if(successor->rightChild != nullptr){
  146.             nodesStack.top()->leftChild = successor->rightChild;
  147.         }else{
  148.             nodesStack.top()->leftChild == nullptr;
  149.         }
  150.         successor->leftChild = nodeToRemove->leftChild;
  151.         successor->rightChild = nodeToRemove->rightChild;
  152.         if(nodeToRemove == root){
  153.             root = successor;
  154.         }
  155.         else{
  156.             while(nodesStack.top() != nodeToRemove && !nodesStack.empty()){
  157.                 nodesStack.pop();
  158.             }
  159.             nodesStack.pop();
  160.             if(nodesStack.top()->leftChild == nodeToRemove){
  161.                 nodesStack.top()->leftChild = successor;
  162.             }else{
  163.                 nodesStack.top()->rightChild = successor;
  164.             }
  165.         }
  166.         delete nodeToRemove;
  167.     }
  168.     //wezel ma lewego potomka
  169.     else if(current->leftChild != nullptr && current->rightChild == nullptr){
  170.         nodesStack.pop();
  171.         if(nodesStack.top()->leftChild == current) {
  172.             nodesStack.top()->leftChild = current->leftChild;
  173.         }else{
  174.             nodesStack.top()->rightChild=current->leftChild;
  175.         }
  176.  
  177.     }
  178.     else if(current->rightChild!=nullptr && current->leftChild == nullptr){
  179.         nodesStack.pop();
  180.         if(nodesStack.top()->leftChild == current){
  181.             nodesStack.top()->leftChild = current->rightChild;
  182.         }else{
  183.             nodesStack.top()->rightChild = current->rightChild;
  184.         }
  185.     }
  186.     return true;
  187. }
  188. //zwraca wskaznik na wezel o podanym kluczu. Zwraca wskaznik na nullptr jesli nie znaleziono klucza.
  189. Node* BinarySearchTree::FindNode(int k){
  190.     Node* current = this->root;
  191.     while((current!=nullptr && current->key!=k))
  192.         if(current->key < k)
  193.                 current = current->rightChild;
  194.             else
  195.                 current = current->leftChild;
  196.  
  197.     return current;
  198. }
  199.  
  200. BinarySearchTree::BinarySearchTree(){
  201.     this->root = nullptr;
  202. }
  203. //zwraca true jesli udalo sie wprowadzic wezel do BST
  204. bool BinarySearchTree::InsertNode(int k){
  205.  
  206.     if (this->root == nullptr){
  207.         this->root = new Node(k);
  208.     }
  209.     Node* current = this->root;
  210.     Node* parent = nullptr;
  211.     while(current!=nullptr){
  212.         if(current->key == k)
  213.             return false;
  214.  
  215.         parent = current;
  216.         if(current->key < k){
  217.             current = current->rightChild;
  218.         }
  219.         else{
  220.             current = current->leftChild;}
  221.     }
  222.  
  223.     if(parent->key >k){
  224.             parent->leftChild = new Node(k);
  225.     }else{
  226.     parent->rightChild = new Node(k);
  227.         }
  228.         return true;
  229.     }
  230.  
  231.  
  232. void BinarySearchTree::InsertNodesBulk(int n){
  233.     int currentInserted = 0;
  234.     while(currentInserted <n){
  235.         if(InsertNode(((rand()%20001)-10000))==true){
  236.             currentInserted++;
  237.         }
  238.     }
  239. }
  240.  
  241. int main()
  242. {
  243.     clock_t begin, end;
  244.     double time_spent;
  245.     FILE* fp = fopen("inlab03.txt", "r");
  246.     int N;
  247.     int k1;
  248.     int k2;
  249.     int k3;
  250.     int k4;
  251.     if (fp == NULL)
  252.         return -1;
  253.     fscanf (fp, "%d %d %d %d %d", &N ,&k1, &k2, &k3, &k4);
  254.     fclose(fp);
  255.     begin = clock();
  256.  
  257.     BinarySearchTree* bst = new BinarySearchTree();
  258.     bst->RemoveNode(k1);
  259.     bst->InsertNode(k1);
  260.     bst->InsertNodesBulk(N);
  261.     bst->scanInorder(bst->root);
  262.     bst->scanPostorder(bst->root);
  263.     bst->InsertNode(k2);
  264.     bst->scanInorder(bst->root);
  265.     bst->InsertNode(k3);
  266.     bst->InsertNode(k4);
  267.     bst->RemoveNode(k1);
  268.     bst->scanPreorder(bst->root);
  269.     bst->FindNode(k1);
  270.     bst->RemoveNode(k2);
  271.     bst->scanInorder(bst->root);
  272.     bst->RemoveNode(k3);
  273.     bst->RemoveNode(k4);
  274.  
  275.     end = clock();
  276.     time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  277.  
  278.     cout << endl << to_string(time_spent);
  279.     return 0;
  280. }
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