Scribd
Upload
130 views30 pages

Dsa Assignment 2

The document contains C code to implement various binary tree operations: 1) Creating a binary tree and inserting nodes. 2) Performing in-order, pre-order and post-order tree traversals. 3) Implementing a binary search tree with functions for finding minimum/maximum nodes, inserting nodes, and deleting nodes. Pseudocode and C code are provided for each operation.

Uploaded by

Devendhiran Dasarathan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
130 views30 pages

Dsa Assignment 2

The document contains C code to implement various binary tree operations: 1) Creating a binary tree and inserting nodes. 2) Performing in-order, pre-order and post-order tree traversals. 3) Implementing a binary search tree with functions for finding minimum/maximum nodes, inserting nodes, and deleting nodes. Pseudocode and C code are provided for each operation.

Uploaded by

Devendhiran Dasarathan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

DATA STRUCTURE AND ANALYS:

Name: Devendhiran.D
Reg no: 21MID0218
Assignment-2
1) Write a program in C to implement a binary tree

// Write a program in c implementation of binary tree

#include<stdio.h>
#include<stdlib.h>

struct node
{
int value;
struct node *left_child, *right_child;
};

struct node *new_node(int value)

{
struct node *tmp = (struct node *)malloc(sizeof(struct node));
tmp->value = value;
tmp->left_child = tmp->right_child = NULL;
return tmp;
}

void print(struct node *root_node)


{
if (root_node != NULL)
{
print(root_node->left_child);
printf("%d \n", root_node->value);
print(root_node->right_child);
}
}

struct node* insert_node(struct node* node, int value)


{

if (node == NULL) return new_node(value);

if (value < node->value)


{
node->left_child = insert_node(node->left_child, value);
}

else if (value > node->value)


{
node->right_child = insert_node(node->right_child, value);
}
return node;
}

int main()
{
printf("Implementation of a Binary Tree in C is:\n\n");

struct node *root_node = NULL;


root_node = insert_node(root_node, 10);
insert_node(root_node, 10);
insert_node(root_node, 30);
insert_node(root_node, 20);
insert_node(root_node, 82);
insert_node(root_node, 62);
insert_node(root_node, 45);
print(root_node);

return 0;
}
Code Screen Shot:
Output:
2)Write a program in C to perform tree traversals (in order, pre order and post order) on a
binary tree

#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int data)


{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

void printPostorder(struct node* node)


{
if (node == NULL)
return;

printPostorder(node->left);

printPostorder(node->right);
printf("%d ", node->data);
}

void printInorder(struct node* node)


{
if (node == NULL)
return;

printInorder(node->left);

printf("%d ", node->data);

printInorder(node->right);
}

void printPreorder(struct node* node)


{
if (node == NULL)
return;

printf("%d ", node->data);

printPreorder(node->left);

printPreorder(node->right);
}

int main()
{
struct node* root = newNode(2);
root->left = newNode(4);
root->right = newNode(6);
root->left->left = newNode(8);
root->left->right = newNode(10);

printf("\nPreorder traversal of binary tree is \n");


printPreorder(root);

printf("\nInorder traversal of binary tree is \n");


printInorder(root);

printf("\nPostorder traversal of binary tree is \n");


printPostorder(root);

getchar();
return 0;
}

Code screen shots:


Output:
3)Write a program in C to implement binary search tree and perform the following
operations on it: FindMin, FindMax, FindX, Insertion and deletion.

i)FindMin and FindMax

/* C Program to find min and max in binary search tree */

#include<stdio.h>
#include<stdlib.h>

struct node
{
struct node *lchild;
int info;
struct node *rchild;
};

struct node *insert(struct node *ptr, int ikey);


struct node *Min(struct node *ptr);
struct node *Max(struct node *ptr);
void display(struct node *ptr,int level);

int main( )
{
struct node *root=NULL,*ptr;
int choice,k;

while(1)
{
printf("\n");
printf("[Link] a element\n");
printf("[Link]\n");
printf("[Link] minimum and maximum\n");
printf("[Link]\n");
printf("\nEnter a your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("\nEnter the key to be inserted : ");
scanf("%d",&k);
root = insert(root, k);
break;

case 2:
printf("\n");
display(root,0);
printf("\n");
break;

case 3:
ptr = Min(root);
if(ptr!=NULL)
printf("\nMinimum key is %d\n", ptr->info );
ptr = Max(root);
if(ptr!=NULL)
printf("\nMaximum key is %d\n", ptr->info );
break;

case 4:
exit(1);

default:
printf("\nWrong choice\n");
}
}

return 0;

struct node *insert(struct node *ptr, int ikey )


{
if(ptr==NULL)
{
ptr = (struct node *) malloc(sizeof(struct node));
ptr->info = ikey;
ptr->lchild = NULL;
ptr->rchild = NULL;
}
else if(ikey < ptr->info)
ptr->lchild = insert(ptr->lchild, ikey);
else if(ikey > ptr->info)
ptr->rchild = insert(ptr->rchild, ikey);
else
printf("\nDuplicate key\n");
return ptr;
}
struct node *Min(struct node *ptr)
{
if(ptr==NULL)
return NULL;
else if(ptr->lchild==NULL)
return ptr;
else
return Min(ptr->lchild);
}

struct node *Max(struct node *ptr)


{
if(ptr==NULL)
return NULL;
else if(ptr->rchild==NULL)
return ptr;
else
return Max(ptr->rchild);
}

void display(struct node *ptr,int level)


{
int i;
if(ptr == NULL )
return;
else
{
display(ptr->rchild, level+1);
printf("\n");
for (i=0; i<level; i++)
printf(" ");
printf("%d", ptr->info);
display(ptr->lchild, level+1);
}
}
Code Screen shot:
Output:
ii) Insertion and deletion of binary search

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct node{
int data;
struct node *left;
struct node *right;
};

struct node *root= NULL;

struct node* createNode(int data){

struct node *newNode = (struct node*)malloc(sizeof(struct node));

newNode->data= data;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

void insert(int data) {

struct node *newNode = createNode(data);


if(root == NULL){
root = newNode;
return;
}
else {

struct node *current = root, *parent = NULL;

while(true) {

parent = current;

if(data < current->data) {


current = current->left;
if(current == NULL) {
parent->left = newNode;
return;
}
}

else {
current = current->right;
if(current == NULL) {
parent->right = newNode;
return;
}
}
}
}
}
struct node* minNode(struct node *root) {
if (root->left != NULL)
return minNode(root->left);
else
return root;
}

struct node* deleteNode(struct node *node, int value) {


if(node == NULL){
return NULL;
}
else {

if(value < node->data)


node->left = deleteNode(node->left, value);

else if(value > node->data)


node->right = deleteNode(node->right, value);

else {
if(node->left == NULL && node->right == NULL)
node = NULL;

else if(node->left == NULL) {


node = node->right;
}

else if(node->right == NULL) {


node = node->left;
}
else {
struct node *temp = minNode(node->right);
node->data = temp->data;
node->right = deleteNode(node->right, temp->data);
}
}
return node;
}
}

void inorderTraversal(struct node *node) {

if(root == NULL){
printf("Tree is empty\n");
return;
}
else {

if(node->left!= NULL)
inorderTraversal(node->left);
printf("%d ", node->data);
if(node->right!= NULL)
inorderTraversal(node->right);

}
}

int main()
{
insert(50);
insert(30);
insert(70);
insert(60);
insert(10);
insert(90);

printf("Binary search tree after insertion: \n");


inorderTraversal(root);

struct node *deletedNode = NULL;


deletedNode = deleteNode(root, 90);
printf("\nBinary search tree after deleting node 90: \n");
inorderTraversal(root);

deletedNode = deleteNode(root, 30);


printf("\nBinary search tree after deleting node 30: \n");
inorderTraversal(root);

deletedNode = deleteNode(root, 50);


printf("\nBinary search tree after deleting node 50: \n");
inorderTraversal(root);

return 0;
}

Code screenshots:
Output:

You might also like