193030

BST - count, search, show path, height, from X uprajnenie na gl. as. Golemanova.

Dec 2nd, 2020
806
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <iostream>
  4. using namespace std;
  5. int counterNodes = 0;
  6. int counterLeaves = 0;
  7.  
  8.     struct Node {
  9.     struct Node* lchild;
  10.     int data;
  11.     struct Node* rchild;
  12. }* root = NULL;
  13. void Insert(int key)
  14. {
  15.     struct Node *p;
  16.     struct Node *t = root;
  17.     struct Node *r = NULL;
  18.  
  19.     if(root == NULL)
  20.     {
  21.         p = new Node;
  22.         p->data = key;
  23.         p->rchild = p->lchild = NULL;
  24.         root = p;
  25.         return;
  26.     }
  27.  
  28.     while(t!=NULL)
  29.     {
  30.         if(key<t->data)
  31.             t = t->lchild;
  32.         if(key>t->data)
  33.             t = t->rchild;
  34.         else
  35.             return;
  36.     }
  37.  
  38.     p = new Node;
  39.     p->data = key;
  40.     p->rchild=p->lchild = NULL;
  41.     if(key < r->data)
  42.     {
  43.         r->lchild = p;
  44.     }
  45.     if(key > r->data)
  46.     {
  47.         r->rchild = p;
  48.     }
  49.  
  50.  
  51.  
  52. }
  53. void Inorder(struct Node* p)
  54. {
  55.     if (p) {
  56.         Inorder(p->lchild);
  57.         printf("%d ", p->data);
  58.         Inorder(p->rchild);
  59.     }
  60. }
  61. struct Node* Search(int key)
  62. {
  63.     struct Node* t = root;
  64.     while (t != NULL) {
  65.         if (key == t->data)
  66.             return t;
  67.         else if (key < t->data)
  68.             t = t->lchild;
  69.         else
  70.             t = t->rchild;
  71.     }
  72.     return NULL;
  73. }
  74. struct Node* RInsert(struct Node* p, int key)
  75. {
  76.     struct Node* t = NULL;
  77.     if (p == NULL) {
  78.         t = new Node;
  79.         t->data = key;
  80.         t->lchild = t->rchild = NULL;
  81.         return t;
  82.     }
  83.     if (key < p->data)
  84.         p->lchild = RInsert(p->lchild, key);
  85.     else if (key > p->data)
  86.         p->rchild = RInsert(p->rchild, key);
  87.     return p;
  88. }
  89.  
  90. // 01. Procedure for counting nodes
  91. void countNodesProcedure(struct Node* p, int &counter)
  92. {
  93.     if(p)
  94.     {
  95.         ++counter;
  96.         countNodesProcedure(p->rchild, counter);
  97.         countNodesProcedure(p->lchild, counter);
  98.     }
  99.  
  100. }
  101.  
  102. // 02. Function for counting nodes
  103. int countNodesFunction(struct Node *p)
  104. {
  105.     int nodesCounter =  1;             //Node itself should be counted
  106.     if (p == NULL)
  107.         return 0;
  108.     else
  109.     {
  110.         nodesCounter += countNodesFunction(p->lchild);
  111.         nodesCounter += countNodesFunction(p->rchild);
  112.         return nodesCounter;
  113.     }
  114.  
  115. }
  116.  
  117. int countLeavesFunction(struct Node *p)
  118. {
  119.     if(p==NULL) {
  120.         return 0;
  121.     }
  122.     if(p->lchild==NULL && p->rchild==NULL)
  123.     {
  124.         return 1;
  125.     }
  126.     return countLeavesFunction(p->lchild) + countLeavesFunction(p->rchild);
  127. }
  128.  
  129.  
  130. void countLeavesProcedure(struct Node *p)
  131. {
  132.  
  133.     if(p)
  134.     {
  135.         if(p->rchild == NULL && p->lchild == NULL)
  136.         {
  137.             counterLeaves++;
  138.         }
  139.         countLeavesProcedure(p->lchild);
  140.         countLeavesProcedure(p->rchild);
  141.     }
  142. }
  143.  
  144. // 05. Function for returning the height of a  tree
  145. int height(struct Node *p)
  146. {
  147.     if(p)
  148.     {
  149.         return 1+ max(height(p->rchild),height(p->lchild));
  150.     }
  151.         return 0;
  152. }
  153.  
  154. // 06. Show path bool check
  155. int existCheck(int key) {
  156.     struct Node* t = root;
  157.     static int counter = 0;
  158.     while (t != NULL) {
  159.         if (key == t->data)
  160.             return 1;
  161.         else if (key < t->data)
  162.         {
  163.             counter++;
  164.             t = t->lchild;
  165.         }
  166.         else
  167.         {
  168.             counter++;
  169.             t = t->rchild;
  170.         }
  171.     }
  172.     return 0;
  173. }
  174.  
  175. // 06. Show Path
  176. void showPathOfKey(int key) {
  177.     if(!existCheck(key))
  178.     {
  179.         cout << "The node with value "  << key << " does not exist." << endl;
  180.         return;
  181.     }
  182.     struct Node* t = root;
  183.     static int counter = 0;
  184.     while (t != NULL) {
  185.         if (key == t->data)
  186.         {
  187.             cout << t->data << endl;
  188.             return;
  189.         }
  190.         else if (key < t->data)
  191.         {
  192.             cout << t->data << endl;
  193.             t = t->lchild;
  194.         }
  195.         else
  196.         {
  197.             cout << t->data << endl;
  198.             t = t->rchild;
  199.         }
  200.     }
  201.     return;
  202. }
  203.  
  204. int main()
  205. {
  206.  
  207.     struct Node* temp;
  208.     root = RInsert(root, 50);
  209.     RInsert(root, 10);
  210.     RInsert(root, 60);
  211.     RInsert(root,70);
  212.     /*
  213.     RInsert(root, 40);
  214.     RInsert(root, 70);
  215.     RInsert(root, 10);3
  216.     */
  217.    // Inorder(root);
  218.     cout << endl;
  219.     // 01. Procedure for counting nodes with &
  220.     /*
  221.     int nodesCounterProcedure = 0;
  222.     countNodesProcedure(root, nodesCounterProcedure);
  223.     cout << "01. (procedure) The number of nodes is: " << nodesCounterProcedure << endl;
  224.     */
  225.  
  226.     // --- TODO!!!!!!!!!!!! - check 06. make it with recursion
  227.  
  228.     // 02. Function for counting nodes
  229.     // cout << "02. (function) The number of nodes is: " << countNodesFunction(root) << endl;
  230.  
  231.     // 03. Count leaves of a tree function
  232.     // cout << "03. (function) The amount of leaves is: " << countLeavesFunction(root) << endl;
  233.  
  234.     // 04. Count leaves of a tree procedure
  235.     // countLeavesProcedure(root);
  236.     // cout << "04. (procedure) The amount of leaves is " << counterLeaves << endl;
  237.  
  238.     // 05. Function for returning the height of the tree
  239.     // cout <<"05. (function) The height of the tree is " << height(root) << endl;
  240.  
  241.     // 06. Procedure WITH FUNCTION for showing the path of the binary tree.
  242.     // showPathOfKey(70);
  243. }
  244.  
RAW Paste Data