Scribd
Upload
41 views12 pages

Program-1: Write A Program To Implement Binary Tree Traversals (Preorder, Inorder and Postorder)

Program 1 implements binary tree traversals (preorder, inorder, postorder) by creating node and tree structures and functions that recursively print the nodes based on traversal order. Program 2 searches a binary search tree for a given element by recursively traversing the tree and comparing keys. Program 3 provides a menu driven program for insertion, deletion, and traversal functions on a binary search tree, allowing the user to create a tree, search, delete and print traversals.

Uploaded by

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

Program-1: Write A Program To Implement Binary Tree Traversals (Preorder, Inorder and Postorder)

Program 1 implements binary tree traversals (preorder, inorder, postorder) by creating node and tree structures and functions that recursively print the nodes based on traversal order. Program 2 searches a binary search tree for a given element by recursively traversing the tree and comparing keys. Program 3 provides a menu driven program for insertion, deletion, and traversal functions on a binary search tree, allowing the user to create a tree, search, delete and print traversals.

Uploaded by

Carl Jackson
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Department of Computer Science & Engineering

Data Structure (CS303)

CSE-III (B)

Lab Assignment- 8

Program-1 : Write a program to implement Binary Tree Traversals


(Preorder, Inorder and Postorder).
Code : // C++ language
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printPostorder(struct Node* node)
{
if (node == NULL)
return;

printPostorder(node->left);
printPostorder(node->right);
cout << node->data << " ";
}
void printInorder(struct Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
cout << node->data << " ";
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct Node* root = newNode(5);
root->left = newNode(10);
root->right = newNode(15);
root->left->left = newNode(20);
root->left->right = newNode(25);
cout << "\nPreorder traversal of binary tree is \n";
printPreorder(root);

cout << "\nInorder traversal of binary tree is \n";


printInorder(root);

cout << "\nPostorder traversal of binary tree is \n";


printPostorder(root);

return 0;
}
Output -

Program-2: Write a program to search an element in Binary Search Tree


(BST).
Code : // C language
#include<stdio.h>
#include<stdlib.h>
struct node{
int key;
struct node *left, *right;
};
struct node *newNode(int item){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void traversetree(struct node *root){
if (root != NULL){
traversetree(root->left);
printf("%d \t", root->key);
traversetree(root->right);
}
}
struct node* search(struct node* root, int key){
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
struct node* insert(struct node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
return node;
}
int main(){
struct node *root = NULL;
root = insert(root, 35);
insert(root, 15);
insert(root, 10);
insert(root, 5);
insert(root, 30);
insert(root, 20);
insert(root, 25);
printf("The tree is :\n");
traversetree(root);
printf("\nSearching for 15 in this tree ");
if(search(root , 15))
printf("\nelement found");
else
printf("\nelement not found");
return 0;
}

Output -

Program-3: Write a menu driven program for insertion, deletion and traversal
in Binary Search Tree (BST).
Code : // C language
#include <stdio.h>
#include <stdlib.h>
struct BST
{
int data;
struct BST *left;
struct BST *right;
};
typedef struct BST NODE;
NODE *node;
NODE* createtree(NODE *node, int data)
{
if (node == NULL)
{
NODE *temp;
temp= (NODE*)malloc(sizeof(NODE));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
if (data < (node->data))
{
node->left = createtree(node->left, data);
}
else if (data > node->data)
{
node -> right = createtree(node->right, data);
}
return node;
}
NODE* search(NODE *node, int data)
{
if(node == NULL)
printf("\nElement not found");
else if(data < node->data)
{
node->left=search(node->left, data);
}
else if(data > node->data)
{
node->right=search(node->right, data);
}
else
printf("\nElement found is: %d", node->data);
return node;
}
void inorder(NODE *node)
{
if(node != NULL)
{
inorder(node->left);
printf("%d\t", node->data);
inorder(node->right);
}
}
void preorder(NODE *node)
{
if(node != NULL)
{
printf("%d\t", node->data);
preorder(node->left);
preorder(node->right);
}
}

void postorder(NODE *node)


{
if(node != NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d\t", node->data);
}
}
NODE* findMin(NODE *node)
{
if(node==NULL)
{
return NULL;
}
if(node->left)
return findMin(node->left);
else
return node;
}
NODE* del(NODE *node, int data)
{
NODE *temp;
if(node == NULL)
{
printf("\nElement not found");
}
else if(data < node->data)
{
node->left = del(node->left, data);
}
else if(data > node->data)
{
node->right = del(node->right, data);
}
else
{ /* Now We can delete this node and replace with either minimum element in the
right sub tree or maximum element in the left subtree */
if(node->right && node->left)
{ /* Here we will replace with minimum element in the right sub tree */
temp = findMin(node->right);
node -> data = temp->data;
/* As we replaced it with some other node, we have to delete that node */
node -> right = del(node->right,temp->data);

}
else
{
/* If there is only one or zero children then we can directly remove it from the tree
and connect its parent to its child */
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp); /* temp is longer required */
}
}
return node;
}
int main()
{
int data, ch, i, n;
NODE *root=NULL;

while (1)
{
printf("\n1.Insertion in Binary Search Tree");
printf("\n2.Search Element in Binary Search Tree");
printf("\n3.Delete Element in Binary Search Tree");
printf("\n4.Inorder\n5.Preorder\n6.Postorder\n7.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch (ch)
{
case 1: printf("\nEnter N value: " );
scanf("%d", &n);
printf("\nEnter the values to create BST like(2,1,9,10,14,3,24,17,7,6,16,28)\n");
for(i=0; i<n; i++)
{
scanf("%d", &data);
root=createtree(root, data);
}
break;
case 2: printf("\nEnter the element to search: ");
scanf("%d", &data);
root=search(root, data);
break;
case 3: printf("\nEnter the element to delete: ");
scanf("%d", &data);
root=del(root, data);
break;
case 4: printf("\nInorder Traversal: \n");
inorder(root);
break;
case 5: printf("\nPreorder Traversal: \n");
preorder(root);
break;
case 6: printf("\nPostorder Traversal: \n");
postorder(root);
break;
case 7: exit(0);
default:printf("\nWrong option");
break;
}
}
return 0;
}

Output -

You might also like