Assignment 1: Binary Search Tree and Traversals
Set A
a) Implement a Binary search tree (BST) library (btree.h) with operations – create, search, insert, inorder, preorder and postorder. Write a menu driven program that performs the above operations.
#include<stdio.h>
#include<stdlib.h>
struct bst
{
int data;
struct bst *lchild,*rchild;
}node;
int cnt=0,leafcnt=0,nleafcnt=0;
struct bst *create()
{
struct bst *temp=(struct bst*)malloc(sizeof(struct bst));
temp->lchild=NULL;
temp->rchild=NULL;
return temp;
}
void insert(struct bst *r, struct bst *new1)
{
if(new1->data < r->data)
{
if(r->lchild==NULL)
r->lchild=new1;
else
insert(r->lchild,new1);
}
if(new1->data > r->data)
{
if(r->rchild==NULL)
r->rchild=new1;
else
insert(r->rchild,new1);
}
}
struct bst *search(struct bst *r, int key)
{
struct bst *temp;
temp=r;
while(temp!=NULL)
{
if(temp->data==key)
return temp;
if(key < temp->data)
temp=temp->lchild;
else
temp=temp->rchild;
}
return NULL;
}
int count(struct bst *temp)
{
if(temp!=NULL)
{
cnt++;
count(temp->lchild);
count(temp->rchild);
}
return cnt;
}
int countleaf(struct bst *temp)
{
if(temp!=NULL)
{
if(temp->lchild==NULL && temp->rchild==NULL)
leafcnt++;
countleaf(temp->lchild);
countleaf(temp->rchild);
}
return leafcnt;
}
int countnleaf(struct bst *temp)
{
if(temp!=NULL)
{
if(temp->lchild!=NULL || temp->rchild!=NULL)
nleafcnt++;
countnleaf(temp->lchild);
countnleaf(temp->rchild);
}
return nleafcnt;
}
void inorder(struct bst *temp)
{
if(temp!=NULL)
{
inorder(temp->lchild);
printf("%d\t",temp->data);
inorder(temp->rchild);
}
}
void postorder(struct bst *temp)
{
if(temp!=NULL)
{
postorder(temp->lchild);
postorder(temp->rchild);
printf("%d\t",temp->data);
}
}
void preorder(struct bst *temp)
{
if(temp!=NULL)
{
printf("%d\t",temp->data);
preorder(temp->lchild);
preorder(temp->rchild);
}
}
void inorder_n(struct bst *r)
{
struct bst *stack[100];
int top=-1;
if(r!=NULL)
{
top++;
stack[top]=r;
r=r->lchild;
while(top>=0)
{
while(r!=NULL)
{
top++;
stack[top]=r;
r=r->lchild;
}
r=stack[top];
top--;
printf("%d\t",r->data);
r=r->rchild;
if(r!=NULL)
{
top++;
stack[top]=r;
r=r->lchild;
}
}
}
}
Save this above code in the stack library file as btree.h
#include<stdio.h>
#include<stdlib.h>
#include "btree.h"
int main()
{
int ch,n,i,value,cnt;
struct bst *newnode,*root,*temp;
root=NULL;
while(1)
{
printf("\n---Binary Search Tree---\n");
printf("1.Insert\n");
printf("2.Search\n");
printf("3.Count Total Nodes\n");
printf("4.Count Leaf Nodes\n");
printf("5.Count Non Leaf Nodes\n");
printf("6.Inorder Traversal (Recursive)\n");
printf("7.Postorder Traversal (Recursive)\n");
printf("8.Preorder Traversal (Recursive)\n");
printf("9.Inorder Traversal (Non Recursive\n");
printf("10.Exit\n");
printf("Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nHow many nodes to create:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
newnode=create();
printf("\nEnter the node data:");
scanf("%d",&newnode->data);
if(root==NULL)
root=newnode;
else
insert(root,newnode);
}
break;
case 2: printf("\nEnter the node value to be searched:");
scanf("%d",&value);
temp=search(root,value);
if(temp==NULL)
printf("\nNode Not Found\n");
else
printf("\nNode Found\n");
break;
case 3: cnt=count(root);
printf("\nTotal Nodes=%d\n",cnt);
break;
case 4: cnt=countleaf(root);
printf("\nTotal Leaf Nodes=%d\n",cnt);
break;
case 5: cnt=countnleaf(root);
printf("\nTotal Non Leaf Nodes=%d\n",cnt);
break;
case 6: printf("\nInorder Traversal=");
inorder(root);
break;
case 7: printf("\nPostorder Traversal=");
postorder(root);
break;
case 8: printf("\nPreorder Traversal=");
preorder(root);
break;
case 9: printf("\nInorder Traversal=");
inorder_n(root);
break;
case 10: exit(0);
default: printf("\nInvalid Choice\n");
}
}
}
b) Write a program which uses binary search tree library and counts the total nodes and total leaf nodes in the tree.
int count(T) – returns the total number of nodes from BST
int countLeaf(T) – returns the total number of leaf nodes from BST
#include<stdio.h>
#include<stdlib.h>
#include "btree.h"
int main()
{
int ch,n,i,value,cnt;
struct bst *newnode,*root,*temp;
root=NULL;
while(1)
{
printf("\n---Binary Search Tree---\n");
printf("1.Insert\n");
printf("2.Search\n");
printf("3.Count Total Nodes\n");
printf("4.Count Leaf Nodes\n");
printf("5.Count Non Leaf Nodes\n");
printf("6.Exit\n");
printf("Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nHow many nodes to create:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
newnode=create();
printf("\nEnter the node data:");
scanf("%d",&newnode->data);
if(root==NULL)
root=newnode;
else
insert(root,newnode);
}
break;
case 2: printf("\nEnter the node value to be searched:");
scanf("%d",&value);
temp=search(root,value);
if(temp==NULL)
printf("\nNode Not Found\n");
else
printf("\nNode Found\n");
break;
case 3: cnt=count(root);
printf("\nTotal Nodes=%d\n",cnt);
break;
case 4: cnt=countleaf(root);
printf("\nTotal Leaf Nodes=%d\n",cnt);
break;
case 5: cnt=countnleaf(root);
printf("\nTotal Non Leaf Nodes=%d\n",cnt);
break;
case 6: exit(0);
default: printf("\nInvalid Choice\n");
}//switch
}//while
}//main
Btree.h
#include<stdio.h>
#include<stdlib.h>
struct bst
{
int data;
struct bst *lchild,*rchild;
}node;
int cnt=0,leafcnt=0,nleafcnt=0;
//creating a new node
struct bst *create()
{
struct bst *temp=(struct bst*)malloc(sizeof(struct bst));
temp->lchild=NULL;
temp->rchild=NULL;
return temp;
}
//inserting a above created node at proper position
void insert(struct bst *r, struct bst *new1)
{
//if new node is less than parent node
if(new1->data < r->data)
{
if(r->lchild==NULL)
r->lchild=new1;
else
insert(r->lchild,new1);
}
//if new node is greater than parent node
if(new1->data > r->data)
{
if(r->rchild==NULL)
r->rchild=new1;
else
insert(r->rchild,new1);
}
}
//to search an element in Binary Search Tree
struct bst *search(struct bst *r, int key)
{
struct bst *temp;
temp=r;
while(temp!=NULL)
{
if(temp->data==key)
return temp;
if(key < temp->data)
temp=temp->lchild;
else
temp=temp->rchild;
}
return NULL;
}
//to count total number of nodes
int count(struct bst *temp)
{
if(temp!=NULL)
{
cnt++;
count(temp->lchild);
count(temp->rchild);
}
return cnt;
}
//to count total number of leaf nodes
int countleaf(struct bst *temp)
{
if(temp!=NULL)
{
if(temp->lchild==NULL && temp->rchild==NULL)
leafcnt++;
countleaf(temp->lchild);
countleaf(temp->rchild);
}
return leafcnt;
}
//to count total number of non leaf nodes
int countnleaf(struct bst *temp)
{
if(temp!=NULL)
{
if(temp->lchild!=NULL || temp->rchild!=NULL)
nleafcnt++;
countnleaf(temp->lchild);
countnleaf(temp->rchild);
}
return nleafcnt;
}
Set B
a) Write a C program which uses Binary search tree library and implements following function with recursion:
T copy(T) – create another BST which is exact copy of BST which is passed as parameter.
int compare(T1, T2) – compares two binary search trees and returns 1 if they are equal and 0
otherwise.
#include <stdio.h>
#include <stdlib.h>
// Structure for BST Node
typedef struct node {
int data;
struct node *left, *right;
} NODE;
// Function to create a new node
NODE* createNode(int value) {
NODE* newNode = (NODE*)malloc(sizeof(NODE));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Function to insert into BST
NODE* insert(NODE* root, int value) {
if (root == NULL) return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else
root->right = insert(root->right, value);
return root;
}
// RECURSIVE COPY FUNCTION
// Creates an exact structural copy of the tree
NODE* copy(NODE* T) {
if (T == NULL) return NULL;
NODE* newNode = createNode(T->data);
newNode->left = copy(T->left);
newNode->right = copy(T->right);
return newNode;
}
// RECURSIVE COMPARE FUNCTION
// Returns 1 if trees are identical, 0 otherwise
int compare(NODE* T1, NODE* T2) {
// Both empty
if (T1 == NULL && T2 == NULL) return 1;
// Both non-empty, compare data and recurse
if (T1 != NULL && T2 != NULL) {
return (T1->data == T2->data &&
compare(T1->left, T2->left) &&
compare(T1->right, T2->right));
}
// One empty, one not
return 0;
}
// Simple Inorder Traversal to verify
void inorder(NODE* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
NODE* tree1 = NULL;
int vals[] = {50, 30, 70, 20, 40};
for(int i = 0; i < 5; i++) tree1 = insert(tree1, vals[i]);
// Test Copy
NODE* tree2 = copy(tree1);
printf("Tree 1 Inorder: "); inorder(tree1);
printf("\nTree 2 (Copy) Inorder: "); inorder(tree2);
// Test Compare
if (compare(tree1, tree2))
printf("\n\nResult: Trees are identical.\n");
else
printf("\n\nResult: Trees are different.\n");
return 0;
}
Set C
a) Write a C program which uses Binary search tree library and implements following two functions:
int sumodd(T) – returns sum of all odd numbers from BST
int sumeven(T) – returns sum of all even numbers from BST
mirror(T) – converts given tree into its mirror image.
1. bstlib.h (BST Library Header)
#ifndef BSTLIB_H
#define BSTLIB_H
#include <stdio.h> // For printf in implementations
#include <stdlib.h> // For malloc
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
// BST operations
Node* createNode(int value);
Node* insert(Node* root, int value);
void inorder(Node* root);
void freeTree(Node* root);
// Assignment functions
int sumodd(Node* t);
int sumeven(Node* t);
void mirror(Node* t);
#endif
2. bstlib.c (BST Library Implementation)
#include "bstlib.h"
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int value) {
if (root == NULL) return createNode(value);
if (value < root->data) {
root->left = insert(root->left, value);
} else if (value > root->data) {
root->right = insert(root->right, value);
}
// Ignore duplicates
return root;
}
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void freeTree(Node* root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}
int sumodd(Node* t) {
if (t == NULL) return 0;
return (t->data % 2 != 0 ? t->data : 0) + sumodd(t->left) + sumodd(t-
>right);
}
int sumeven(Node* t) {
if (t == NULL) return 0;
return (t->data % 2 == 0 ? t->data : 0) + sumeven(t->left) + sumeven(t-
>right);
}
void mirror(Node* t) {
if (t == NULL) return;
Node* temp = t->left;
t->left = t->right;
t->right = temp;
mirror(t->left);
mirror(t->right);
}
3. main.c (Program Using BST Library)
#include "bstlib.h"
int main() {
Node* root = NULL;
int values[] = {50, 30, 20, 40, 70, 60, 80, 15, 25, 35, 45};
int n = sizeof(values)/sizeof(values[0]);
// Build BST
for (int i = 0; i < n; i++) {
root = insert(root, values[i]);
}
printf("Original BST (inorder): ");
inorder(root);
printf("\n");
printf("Sum of odd numbers: %d\n", sumodd(root));
printf("Sum of even numbers: %d\n", sumeven(root));
mirror(root);
printf("Mirror BST (inorder): ");
inorder(root);
printf("\n");
freeTree(root);
return 0;
}
No comments:
Post a Comment