NicholasAdamou

Binary Search Tree (C)

Oct 7th, 2019
490
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.29 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. /**
  6.  * Exercise 1: programming in the C language
  7.  * Using the C language, write a program that:
  8.  *    - fills an array with random integers in the range 10 to 99.
  9.  *    - builds a binary search tree by inserting the integers in the array into a tree.
  10.  *    - finds the length of a given BST.
  11.  *    - finds the number of leaf nodes.
  12.  *    - finds the minimum value in a given BST.
  13.  *    - prints the BST in 2D in reverse in-order traversal.
  14.  *    - traverses the tree with pre-order, in-order, and post-order algorithms, printing each value in the tree along the way.
  15.  *
  16.  * author: Nicholas Adamou
  17.  * date: 9/24/19
  18.  * Class: CSC-315
  19.  */
  20.  
  21. typedef struct node Node;
  22.  
  23. #define SIZE 10 // number of nodes in the BST
  24. #define COUNT 4 // default number of spaces
  25.  
  26. struct node
  27. {
  28.     int value;   // node will store an integer
  29.     Node *right; // right child
  30.     Node *left;  // left child
  31. };
  32.  
  33. // function to create a node
  34. Node *new_node(int x)
  35. {
  36.     Node *p = malloc(sizeof(Node));
  37.  
  38.     p->value = x;
  39.     p->left = NULL;
  40.     p->right = NULL;
  41.  
  42.     return p;
  43. }
  44.  
  45. Node *insert(Node *root, int x)
  46. {
  47.     // searching for the place to insert
  48.     if (root == NULL)
  49.         return new_node(x);
  50.     else if (x > root->value) // x is greater. Should be inserted to right
  51.         root->right = insert(root->right, x);
  52.     else // x is smaller. Should be inserted to left
  53.         root->left = insert(root->left, x);
  54.     return root;
  55. }
  56.  
  57. // Function to print binary tree in 2D
  58. // It does reverse in-order traversal
  59. void print2DUtil(Node *root, int depth)
  60. {
  61.     if (root == NULL) // Base case
  62.         return;
  63.  
  64.     depth += COUNT; // Increase distance between levels
  65.  
  66.     print2DUtil(root->right, depth); // Process right child first
  67.  
  68.     // Print current node after space count
  69.     printf("\n");
  70.     for (int i = COUNT; i < depth; i++)
  71.         printf(" ");
  72.     printf("%d\n", root->value);
  73.  
  74.     print2DUtil(root->left, depth); // Process left child last
  75. }
  76.  
  77. // Wrapper over print2DUtil()
  78. void print2D(Node *root)
  79. {
  80.     // Pass initial depth as 0
  81.     print2DUtil(root, 0);
  82. }
  83.  
  84. int length(Node *root)
  85. {
  86.     if (root == NULL)
  87.         return 0;
  88.     else
  89.     {
  90.         return 1 + length(root->left) + length(root->right);
  91.     }
  92. }
  93.  
  94. int getNumberOfLeafNodes(Node *node)
  95. {
  96.     if (node == NULL)
  97.         return 0;
  98.  
  99.     if (node->left == NULL && node->right == NULL)
  100.         return 1;
  101.     else
  102.     {
  103.         return getNumberOfLeafNodes(node->left) +
  104.                getNumberOfLeafNodes(node->right);
  105.     }
  106. }
  107.  
  108. // function to find the minimum value in a node
  109. Node *findMinimum(Node *root)
  110. {
  111.     if (root == NULL)
  112.         return NULL;
  113.     else if (root->left != NULL)         // node with minimum value will have no left child
  114.         return find_minimum(root->left); // left most element will be minimum
  115.  
  116.     return root;
  117. }
  118.  
  119. void preorder(Node *root)
  120. {
  121.     if (root != NULL) // checking if the root is not null
  122.     {
  123.         printf(" %d ", root->value); // printing value at root
  124.         preorder(root->left);        // visiting left child
  125.         preorder(root->right);       // visiting right child
  126.     }
  127. }
  128.  
  129. void inorder(Node *root)
  130. {
  131.     if (root != NULL) // checking if the root is not null
  132.     {
  133.         inorder(root->left);         // visiting left child
  134.         printf(" %d ", root->value); // printing value at root
  135.         inorder(root->right);        // visiting right child
  136.     }
  137. }
  138.  
  139. void postorder(Node *root)
  140. {
  141.     if (root != NULL) // checking if the root is not null
  142.     {
  143.         postorder(root->left);       // visiting left child
  144.         postorder(root->right);      // visiting right child
  145.         printf(" %d ", root->value); // printing value at root
  146.     }
  147. }
  148.  
  149. int main()
  150. {
  151.     int n; // random number
  152.  
  153.     int min = 10; // min number a given node can hold
  154.     int max = 99; // max number a given node can hold
  155.  
  156.     Node *root = new_node(rand() % (max - min + 1) + min);
  157.  
  158.     srand(time(0)); // Use current time as seed for random generator
  159.  
  160.     for (int i = 0; i < SIZE; i++)
  161.     {
  162.         n = (rand() % (max - min + 1) + min);
  163.  
  164.         insert(root, n);
  165.     }
  166.  
  167.     printf("Preorder traversal of the BST:\n");
  168.     preorder(root);
  169.     printf("\n\n");
  170.  
  171.     printf("Inorder traversal of the BST:\n");
  172.     inorder(root);
  173.     printf("\n\n");
  174.  
  175.     printf("Postorder traversal of the BST:\n");
  176.     postorder(root);
  177.     printf("\n\n");
  178.  
  179.     printf("Number of Nodes: %d\n", getFullCount(root));
  180.  
  181.     printf("Number of Leaf Nodes: %d\n", getLeafCount(root));
  182.  
  183.     printf("Minimum value: %d\n", findMinimum(root)->value);
  184.  
  185.     print2D(root);
  186.  
  187.     return 0;
  188. }
Advertisement
Add Comment
Please, Sign In to add comment