Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- /**
- * Exercise 1: programming in the C language
- * Using the C language, write a program that:
- * - fills an array with random integers in the range 10 to 99.
- * - builds a binary search tree by inserting the integers in the array into a tree.
- * - finds the length of a given BST.
- * - finds the number of leaf nodes.
- * - finds the minimum value in a given BST.
- * - prints the BST in 2D in reverse in-order traversal.
- * - traverses the tree with pre-order, in-order, and post-order algorithms, printing each value in the tree along the way.
- *
- * author: Nicholas Adamou
- * date: 9/24/19
- * Class: CSC-315
- */
- typedef struct node Node;
- #define SIZE 10 // number of nodes in the BST
- #define COUNT 4 // default number of spaces
- struct node
- {
- int value; // node will store an integer
- Node *right; // right child
- Node *left; // left child
- };
- // function to create a node
- Node *new_node(int x)
- {
- Node *p = malloc(sizeof(Node));
- p->value = x;
- p->left = NULL;
- p->right = NULL;
- return p;
- }
- Node *insert(Node *root, int x)
- {
- // searching for the place to insert
- if (root == NULL)
- return new_node(x);
- else if (x > root->value) // x is greater. Should be inserted to right
- root->right = insert(root->right, x);
- else // x is smaller. Should be inserted to left
- root->left = insert(root->left, x);
- return root;
- }
- // Function to print binary tree in 2D
- // It does reverse in-order traversal
- void print2DUtil(Node *root, int depth)
- {
- if (root == NULL) // Base case
- return;
- depth += COUNT; // Increase distance between levels
- print2DUtil(root->right, depth); // Process right child first
- // Print current node after space count
- printf("\n");
- for (int i = COUNT; i < depth; i++)
- printf(" ");
- printf("%d\n", root->value);
- print2DUtil(root->left, depth); // Process left child last
- }
- // Wrapper over print2DUtil()
- void print2D(Node *root)
- {
- // Pass initial depth as 0
- print2DUtil(root, 0);
- }
- int length(Node *root)
- {
- if (root == NULL)
- return 0;
- else
- {
- return 1 + length(root->left) + length(root->right);
- }
- }
- int getNumberOfLeafNodes(Node *node)
- {
- if (node == NULL)
- return 0;
- if (node->left == NULL && node->right == NULL)
- return 1;
- else
- {
- return getNumberOfLeafNodes(node->left) +
- getNumberOfLeafNodes(node->right);
- }
- }
- // function to find the minimum value in a node
- Node *findMinimum(Node *root)
- {
- if (root == NULL)
- return NULL;
- else if (root->left != NULL) // node with minimum value will have no left child
- return find_minimum(root->left); // left most element will be minimum
- return root;
- }
- void preorder(Node *root)
- {
- if (root != NULL) // checking if the root is not null
- {
- printf(" %d ", root->value); // printing value at root
- preorder(root->left); // visiting left child
- preorder(root->right); // visiting right child
- }
- }
- void inorder(Node *root)
- {
- if (root != NULL) // checking if the root is not null
- {
- inorder(root->left); // visiting left child
- printf(" %d ", root->value); // printing value at root
- inorder(root->right); // visiting right child
- }
- }
- void postorder(Node *root)
- {
- if (root != NULL) // checking if the root is not null
- {
- postorder(root->left); // visiting left child
- postorder(root->right); // visiting right child
- printf(" %d ", root->value); // printing value at root
- }
- }
- int main()
- {
- int n; // random number
- int min = 10; // min number a given node can hold
- int max = 99; // max number a given node can hold
- Node *root = new_node(rand() % (max - min + 1) + min);
- srand(time(0)); // Use current time as seed for random generator
- for (int i = 0; i < SIZE; i++)
- {
- n = (rand() % (max - min + 1) + min);
- insert(root, n);
- }
- printf("Preorder traversal of the BST:\n");
- preorder(root);
- printf("\n\n");
- printf("Inorder traversal of the BST:\n");
- inorder(root);
- printf("\n\n");
- printf("Postorder traversal of the BST:\n");
- postorder(root);
- printf("\n\n");
- printf("Number of Nodes: %d\n", getFullCount(root));
- printf("Number of Leaf Nodes: %d\n", getLeafCount(root));
- printf("Minimum value: %d\n", findMinimum(root)->value);
- print2D(root);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment