DATA STRUCTURE :ASSIGNMENT NO.8:TREE
PRACTICE PROGRAM:
1) Write a C program to find all the ancestors or descendent of a given node in a binary tree.
ANS:
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left, *right;
} TREE;
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
typedef struct queue
{
TREE *data[MAX];
int front, rear;
} QUEUE;
typedef struct stack
{
TREE *data[MAX];
int top;
} STACK;
int isEmptyStack(STACK *s)
{
return (s->top == -1) ? 1 : 0;
}
int isFullStack(STACK *s)
{
return (s->top == MAX - 1) ? 1 : 0;
}
void push(STACK *s, TREE *t)
{
if (isFullStack(s))
{
printf("\n Stack is Full!");
}
else
{
s->top++;
s->data[s->top] = t;
}
}
TREE *pop(STACK *s)
{
TREE *t;
if (isEmptyStack(s))
{
printf("\n Stack is Empty!");
}
else
{
t = s->data[s->top];
s->top--;
}
return t;
}
int isEmptyQueue(QUEUE *q)
{
return (q->front == -1 && q->rear == -1) ? 1 : 0;
}
int isFullQueue(QUEUE *q)
{
return (q->rear == MAX - 1) ? 1 : 0;
}
void initQueue(QUEUE *q)
{
q->rear = -1;
q->front = -1;
}
void insertQueue(QUEUE *q, TREE *t)
{
if (isFullQueue(q))
{
printf("\n Queue is Full!");
}
else
{
if (isEmptyQueue(q))
{
q->front++;
q->rear++;
q->data[q->rear] = t;
}
else
{
q->rear++;
q->data[q->rear] = t;
}
}
}
void deleteQueue(QUEUE *q)
{
if (isFullQueue(q))
{
printf("\n Queue is Full!");
}
else
{
if (q->rear == q->front)
{
initQueue(q);
}
else
{
q->front++;
}
}
}
TREE *peek(QUEUE *q)
{
TREE *t;
t = q->data[q->front];
return t;
}
TREE *create(TREE *t)
{
int i, n;
TREE *new_node, *temp;
QUEUE *q = NULL;
initQueue(q);
printf("\n Enter size of tree:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->left = NULL;
new_node->right = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
insertQueue(q, t);
}
else
{
temp = peek(q);
if (isEmpty(temp->left))
{
temp->left = new_node;
insertQueue(q, temp->left);
}
else
{
if (isEmpty(temp->right))
{
temp->right = new_node;
insertQueue(q, temp->right);
deleteQueue(q);
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
void ancestors(TREE *t, int n)
{
TREE *temp, *tr;
STACK s1, s2, s3;
s1.top = -1;
s2.top = -1;
s3.top = -1;
temp = t;
push(&s1, temp);
while (!isEmpty(temp))
{
push(&s1, temp->left);
if (!isEmpty(temp->right))
{
push(&s1, temp->right);
push(&s2, temp->right);
}
if (temp->data == n)
break;
temp = temp->left;
}
while (!isEmptyStack(&s2))
{
temp = pop(&s2);
while (!isEmpty(temp))
{
push(&s1, temp->left);
if (!isEmpty(temp->right))
{
push(&s1, temp->right);
push(&s2, temp->right);
}
temp = temp->left;
}
}
while (!isEmptyStack(&s1))
{
temp = pop(&s1);
if (temp->data == n)
{
push(&s3, temp);
tr = temp;
}
else
{
if (temp->left == tr || temp->right == tr)
{
push(&s3, temp);
tr = temp;
}
}
}
while (!isEmptyStack(&s3))
{
temp = pop(&s3);
if (temp->data != n)
printf("\t%d", temp->data);
}
}
void decent(TREE *t, int n)
{
TREE *temp, *tr;
STACK s1, s2;
s1.top = s2.top = -1;
temp = t;
while (!isEmpty(temp))
{
if (temp->data == n)
{
push(&s1, temp);
}
else
{
push(&s2, temp->right);
}
temp = temp->left;
}
while (!isEmptyStack(&s2))
{
temp = pop(&s2);
while (!isEmpty(temp))
{
if (temp->data == n)
{
push(&s1, temp);
}
else
{
push(&s2, temp->right);
}
temp = temp->left;
}
}
while (!isEmptyStack(&s1))
{
temp = pop(&s1);
while (!isEmpty(temp))
{
if (!isEmpty(temp->right))
{
push(&s1, temp->right);
}
printf("\t%d", temp->data);
temp = temp->left;
}
}
}
int main()
{
int n, choice;
TREE *t = NULL;
clrscr();
do
{
printf("\n ------------");
printf("\n1.create\n2.display\n3.ancestors\n4.Exit");
printf("\n-------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
t = create(t);
break;
case 2:
printf("\n The Tree is:\n");
display(t);
break;
case 3:
printf("\n Enter data for finding ancestors:");
scanf("%d", &n);
ancestors(t, n);
break;
case 4:
printf("\n Enter data for finding descendent:");
scanf("%d", &n);
decent(t, n);
break;
}
} while (choice != 5);
getch();
return 0;
}
----------------------------------------------------------------------------------------
3) Write a C program to create binary search tree of integers and perform following
operations using non- recursive functions
- Preorder traversal
- Inorder traversal
- Postorder traversal
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left, *right;
} TREE;
typedef struct stack
{
TREE *data[MAX];
int top;
} STACK;
// function for stack empty or not
int isEmptyStack(STACK *s)
{
return (s->top == -1) ? 1 : 0;
}
// function for stack full or not
int isFullStack(STACK *s)
{
return (s->top == MAX - 1) ? 1 : 0;
}
// function for push into stack
void push(STACK *s, TREE *t)
{
if (isFullStack(s))
{
printf("\n The stack is full!");
}
else
{
s->top++;
s->data[s->top] = t;
}
}
// function for pop from stack
TREE *pop(STACK *s)
{
TREE *t = NULL;
if (isEmptyStack(s))
{
printf("\n The stack is Empty!");
}
else
{
t = s->data[s->top];
s->top--;
}
return t;
}
// Empty tree function
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
// creating binary search tree
TREE *create(TREE *t)
{
int i, n;
TREE *temp, *new_node;
printf("\n Enter size of tree:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->left = NULL;
new_node->right = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
else
{
if (temp->data <= new_node->data)
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
void preOrder(TREE *t)
{
TREE *temp;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
printf("\t%d", temp->data);
push(&s, temp->right);
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
while (!isEmpty(temp))
{
printf("\t%d", temp->data);
push(&s,temp->right);
temp = temp->left;
}
}
}
void postOrder(TREE *t)
{
TREE *temp;
STACK s, s1;
s.top = s1.top = -1;
temp = t;
push(&s, temp);
while (!isEmptyStack(&s))
{
temp = pop(&s);
push(&s1, temp);
if (!isEmpty(temp->left))
{
push(&s, temp->left);
}
if (!isEmpty(temp->right))
{
push(&s, temp->right);
}
}
while (!isEmptyStack(&s1))
{
temp = pop(&s1);
printf("\t%d", temp->data);
}
}
void inOrder(TREE *t)
{
TREE *temp;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
push(&s, temp);
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
printf("\t%d", temp->data);
temp = temp->right;
while (!isEmpty(temp))
{
push(&s, temp);
temp = temp->left;
}
}
}
int main()
{
int choice, n;
TREE *t = NULL;
do
{
printf("\n-------------------");
printf("\n1.create\n2.display\n3.pre-order\n4.post-order\n5.in-order\n6.Exit");
printf("\n-------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
t = create(t);
break;
case 2:
printf("\n The Tree is:\n");
display(t);
break;
case 3:
preOrder(t);
break;
case 4:
postOrder(t);
break;
case 5:
inOrder(t);
break;
}
} while (choice != 6);
getch();
return 0;
}
----------------------------------------------------------------------------------------------------
SET A:
1) Write C programs to implement create and display operation for binary tree.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left;
struct tree *right;
} TREE;
typedef struct queue
{
TREE *data[MAX];
int front, rear;
} QUEUE;
void initQueue(QUEUE *q)
{
q->front = q->rear = -1;
}
int isEmptyQueue(QUEUE *q)
{
return (q->front == -1 && q->rear == -1) ? 1 : 0;
}
int isFullQueue(QUEUE *q)
{
return (q->rear == MAX - 1) ? 1 : 0;
}
void insert(QUEUE *q, TREE *t)
{
if (isFullQueue(q))
{
printf("\n The Queue is Full!");
}
else
{
if (isEmptyQueue(q))
{
q->rear++;
q->front++;
q->data[q->rear] = t;
}
else
{
q->rear++;
q->data[q->rear] = t;
}
}
}
void delete(QUEUE *q)
{
if (isEmptyQueue(q))
{
printf("\n The Queue is Empty!");
}
else
{
if (q->front == q->rear)
{
initQueue(q);
}
else
{
q->front++;
}
}
}
TREE *peek(QUEUE *q)
{
TREE *t = NULL;
if (isEmptyQueue(q))
{
printf("\n The Queue is Empty!");
}
else
{
t = q->data[q->front];
return t;
}
}
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
TREE *create(TREE *t)
{
TREE *new_node, *temp;
QUEUE *q;
initQueue(q);
int n, i;
printf("\n Enter how many nodes you want:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
new_node->left = NULL;
new_node->right = NULL;
if (isEmpty(t))
{
t = new_node;
insert(q, t);
}
else
{
temp = peek(q);
if (isEmpty(temp->left))
{
temp->left = new_node;
insert(q, temp->left);
}
else
{
if (isEmpty(temp->right))
{
temp->right = new_node;
insert(q, temp->right);
delete (q);
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
int main()
{
TREE *t = NULL;
t = create(t);
printf("\n The tree is:\n");
display(t);
getch();
return 0;
}
---------------------------------------------------------------------------
2) Write C programs to implement create and display operation for binary search tree.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct tree
{
int data;
struct tree *left;
struct tree *right;
} TREE;
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
TREE *create(TREE *t)
{
TREE *new_node, *temp;
int i, n;
printf("\n Enter how many nodes you want:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->left = NULL;
new_node->right = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
else
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
return t;
}
void display(TREE*t)
{
if(!isEmpty(t))
{
printf("\t%d",t->data);
display(t->left);
display(t->right);
}
}
int main()
{
TREE*t=NULL;
t=create(t);
printf("\n The Tree is:\n");
display(t);
getch();
return 0;
}
----------------------------------------------------------------------
3) Write a C Program to find the product of all leaf nodes of a binary tree.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left;
struct tree *right;
} TREE;
typedef struct queue
{
TREE *data[MAX];
int front, rear;
} QUEUE;
typedef struct stack
{
TREE *data[MAX];
int top;
} STACK;
// stack operations start here!
void push(STACK *s, TREE* t)
{
if (s->top == MAX - 1)
{
printf("\n Stack is Full!");
}
else
{
s->top++;
s->data[s->top] = t;
}
}
TREE* pop(STACK *s)
{
TREE* n;
if (s->top == -1)
{
printf("\n Stack is Empty!");
}
else
{
n = s->data[s->top];
s->top--;
}
return n;
}
// Queue operations start here!
void initQueue(QUEUE *q)
{
q->front = q->rear = -1;
}
int isEmptyQueue(QUEUE *q)
{
return (q->front == -1 && q->rear == -1) ? 1 : 0;
}
int isFullQueue(QUEUE *q)
{
return (q->rear == MAX - 1) ? 1 : 0;
}
void insert(QUEUE *q, TREE *t)
{
if (isFullQueue(q))
{
printf("\n The Queue is Full!");
}
else
{
if (isEmptyQueue(q))
{
q->rear++;
q->front++;
q->data[q->rear] = t;
}
else
{
q->rear++;
q->data[q->rear] = t;
}
}
}
void deleteQ(QUEUE *q)
{
if (isEmptyQueue(q))
{
printf("\n The Queue is Empty!");
}
else
{
if (q->front == q->rear)
{
initQueue(q);
}
else
{
q->front++;
}
}
}
TREE *peek(QUEUE *q)
{
TREE *t = NULL;
if (isEmptyQueue(q))
{
printf("\n The Queue is Empty!");
}
else
{
t = q->data[q->front];
}
return t;
}
// tree operations start here!
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
TREE *create(TREE *t)
{
int n,i;
TREE *new_node, *temp;
QUEUE *q;
initQueue(q);
printf("\n Enter how many nodes you want:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
new_node->left = NULL;
new_node->right = NULL;
if (isEmpty(t))
{
t = new_node;
insert(q, t);
}
else
{
temp = peek(q);
if (isEmpty(temp->left))
{
temp->left = new_node;
insert(q, temp->left);
}
else
{
if (isEmpty(temp->right))
{
temp->right = new_node;
insert(q, temp->right);
deleteQ(q);
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
int leafProduct(TREE *t)
{
TREE *temp;
STACK *s1,*s2;
int p = 1;
s1->top=s2->top=-1;
temp = t;
while (!isEmpty(temp))
{
if (isEmpty(temp->left) && isEmpty(temp->right))
{
push(s1,temp);
}
if (!isEmpty(temp->right))
{
push(s2, temp->right);
}
temp = temp->left;
}
while (s2->top != -1)
{
temp = pop(s2);
while (!isEmpty(temp))
{
if (isEmpty(temp->left) && isEmpty(temp->right))
{
push(s1, temp);
}
if (!isEmpty(temp->right))
{
push(s2, temp->right);
}
temp = temp->left;
}
}
while (s1->top != -1)
{
p = p * pop(s1)->data;
}
return p;
}
// main function start here!
int main()
{
int p;
TREE *t = NULL;
t = create(t);
printf("\n The tree is:\n");
display(t);
p = leafProduct(t);
printf("\n The product is:%d", p);
getch();
return 0;
}
-----------------------------------------------------------------------
SET B:
1) Write a C Program to implement the following functions on Binary Search Tree
- To insert a new element in the tree.
- To search an element in tree and give the proper message.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct tree
{
int data;
struct tree *left;
struct tree *right;
} TREE;
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
TREE *create(TREE *t)
{
int n, i;
TREE *new_node, *temp;
printf("\n Enter size of tree:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->left = NULL;
new_node->right = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
if (temp->data <= new_node->data)
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
TREE *insert(TREE *t, int n)
{
TREE *new_node, *temp;
new_node = (TREE *)malloc(sizeof(TREE));
new_node->left = NULL;
new_node->right = NULL;
new_node->data = n;
if (isEmpty(t))
{
printf("\n The tree is Empty!");
return t;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
else
{
if (temp->data <= new_node->data)
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
return t;
}
TREE *search(TREE *t, int n)
{
int flag = 0;
TREE *temp;
if (isEmpty(t))
{
printf("\n Tree is Empty!");
return t;
}
else
{
temp = t;
while (t)
{
if (temp->data == n)
{
flag = 1;
printf("\n The element founded at %u position.", temp);
break;
}
if (temp->data <= n)
{
if (!isEmpty(temp->right))
{
temp = temp->right;
}
else
{
break;
}
}
else
{
if (!isEmpty(temp->left))
{
temp = temp->left;
}
else
{
break;
}
}
}
}
if (flag == 0)
{
printf("\n Element not found!");
}
return t;
}
int main()
{
int n, choice;
TREE *t = NULL;
do
{
printf("\n---------------");
printf("\n1.create BST\n2.display\n3.insert\n4.search\n5.Exit");
printf("\n---------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
t = create(t);
break;
case 2:
printf("\n The Tree is:\n");
display(t);
break;
case 3:
printf("\n Enter element for insert:");
scanf("%d", &n);
t = insert(t, n);
break;
case 4:
printf("\n Enter element for search:");
scanf("%d", &n);
t = search(t, n);
break;
}
} while (choice != 5);
getch();
return 0;
}
--------------------------------------------------------------------------------------------------
2) Write a C Program to implement the following functions on Binary Search Tree
- To create mirror image of the tree.
- To count non-leaf nodes.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left, *right;
} TREE;
typedef struct stack
{
TREE *data[MAX];
int top;
} STACK;
int isEmptyStack(STACK *s)
{
return (s->top == -1) ? 1 : 0;
}
int isFullStack(STACK *s)
{
return (s->top == MAX - 1) ? 1 : 0;
}
void push(STACK *s, TREE *t)
{
if (isFullStack(s))
{
printf("\n Stack is Full!");
}
else
{
s->top++;
s->data[s->top] = t;
}
}
TREE *pop(STACK *s)
{
TREE *t;
if (isEmptyStack(s))
{
printf("\n Stack is Empty!");
}
else
{
t = s->data[s->top];
s->top--;
}
return t;
}
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
TREE *create(TREE *t)
{
TREE *temp = NULL, *new_node;
int i, n;
printf("\n Enter Size of tree:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->right = NULL;
new_node->left = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
else
{
if (temp->data <= new_node->data)
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
TREE *mirrorImage(TREE *t)
{
TREE *temp, *temp1;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
temp1 = temp->right;
temp->right = temp->left;
temp->left = temp1;
push(&s, temp->right);
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
while (!isEmpty(temp))
{
temp1 = temp->right;
temp->right = temp->left;
temp->left = temp1;
push(&s, temp->right);
temp = temp->left;
}
}
return t;
}
void countNonLeaf(TREE *t)
{
int count = 0;
TREE *temp;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
if (!isEmpty(temp->left) || !isEmpty(temp->right))
{
count++;
}
if (!isEmpty(temp->right))
{
push(&s, temp->right);
}
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
while (!isEmpty(temp))
{
if (!isEmpty(temp->left) || !isEmpty(temp->right))
{
count++;
}
if (!isEmpty(temp->right))
{
push(&s, temp->right);
}
temp = temp->left;
}
}
printf("\n Total Non-leaf nodes are:%d", count);
}
int main()
{
int choice, n;
TREE *t = NULL, *t1 = NULL;
do
{
printf("\n ---------------");
printf("\n1.create\n2.display\n3.mirror image\n4.count non-leaf node\n5.Exit");
printf("\n ---------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
t = create(t);
break;
case 2:
printf("\n The Tree is:\n");
display(t);
break;
case 3:
t1 = mirrorImage(t);
display(t1);
break;
case 4:
countNonLeaf(t);
break;
}
} while (choice != 5);
getch();
return 0;
}
-----------------------------------------------------------------------------------------------------
3) Write a C Program to implement the following functions on Binary Search Tree
- To count leaf nodes.
- To count total number of nodes.
ANS:
//Non-Recursive program....
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left, *right;
} TREE;
typedef struct stack
{
TREE *data[MAX];
int top;
} STACK;
int isEmptyStack(STACK *s)
{
return (s->top == -1) ? 1 : 0;
}
int isFullStack(STACK *s)
{
return (s->top == MAX - 1) ? 1 : 0;
}
void push(STACK *s, TREE *t)
{
if (isFullStack(s))
{
printf("\n Stack is Full!");
}
else
{
s->top++;
s->data[s->top] = t;
}
}
TREE *pop(STACK *s)
{
TREE *t;
if (isEmptyStack(s))
{
printf("\n Stack is Empty!");
}
else
{
t = s->data[s->top];
s->top--;
}
return t;
}
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
TREE *create(TREE *t)
{
TREE *temp = NULL, *new_node;
int i, n;
printf("\n Enter Size of tree:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->right = NULL;
new_node->left = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
else
{
if (temp->data <= new_node->data)
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
int countLeaf(TREE *t)
{
int count = 0;
TREE *temp;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
if (isEmpty(temp->left) && isEmpty(temp->right))
{
count++;
}
push(&s, temp->right);
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
while (!isEmpty(temp))
{
if (isEmpty(temp->left) && isEmpty(temp->right))
{
count++;
}
push(&s, temp->right);
temp = temp->left;
}
}
return count;
}
int allNodes(TREE *t)
{
int count = 0;
TREE *temp;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
if (!isEmpty(temp))
{
count++;
}
push(&s, temp->right);
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
while (!isEmpty(temp))
{
if (!isEmpty(temp))
{
count++;
}
push(&s, temp->right);
temp = temp->left;
}
}
return count;
}
int main()
{
TREE *t = NULL;
int count1 = 0, count2 = 0, choice;
do
{
printf("\n -----------------------");
printf("\n1.create\n2.display\n3.count all nodes\n4.count leaf nodes\n5.Exit");
printf("\n------------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
t = create(t);
break;
case 2:
printf("\n The Tree is:\n");
display(t);
break;
case 3:
count1 = allNodes(t);
printf("\n Total nodes are:%d", count1);
break;
case 4:
count2 = countLeaf(t);
printf("\n Total leaf nodes are:%d", count2);
break;
}
} while (choice != 5);
getch();
return 0;
}
//Recursive function program.....
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left, *right;
} TREE;
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
TREE *create(TREE *t)
{
TREE *temp = NULL, *new_node;
int i, n;
printf("\n Enter Size of tree:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->right = NULL;
new_node->left = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
else
{
if (temp->data <= new_node->data)
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
int countLeaf(TREE *t)
{
if (isEmpty(t))
{
return 0;
}
if (isEmpty(t->left) && isEmpty(t->right))
{
return 1;
}
return (countLeaf(t->left) + countLeaf(t->right));
}
int allNodes(TREE *t)
{
int i;
if (isEmpty(t))
{
return 0;
}
i = 1 + allNodes(t->left) + allNodes(t->right);
return (i);
}
int main()
{
TREE *t = NULL;
int count1 = 0, count2 = 0, choice;
do
{
printf("\n -----------------------");
printf("\n1.create\n2.display\n3.count all nodes\n4.count leaf nodes\n5.Exit");
printf("\n------------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
t = create(t);
break;
case 2:
printf("\n The Tree is:\n");
display(t);
break;
case 3:
count1 = allNodes(t);
printf("\n Total nodes are:%d", count1);
break;
case 4:
count2 = countLeaf(t);
printf("\n Total leaf nodes are:%d", count2);
break;
}
} while (choice != 5);
getch();
return 0;
}
------------------------------------------------------------------------------------------------------
SET C:
1) Write C programs to create and display the elements using Inorder traversal.
ANS:
//Non-recursive functions....
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left;
struct tree *right;
} TREE;
typedef struct queue
{
TREE *item[MAX];
int front, rear;
} QUEUE;
typedef struct stack
{
TREE *item[MAX];
int top;
} STACK;
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
int isEmptyQueue(QUEUE *q)
{
return (q->front == -1 && q->rear == -1) ? 1 : 0;
}
int isFullQueue(QUEUE *q)
{
return (q->rear == MAX - 1) ? 1 : 0;
}
void initQueue(QUEUE *q)
{
q->front = q->rear = -1;
}
void insert(QUEUE *q, TREE *t)
{
if (isFullQueue(q))
{
printf("\n Queue is Full!");
}
else
{
if (q->front == -1 && q->rear == -1)
{
q->front++;
q->rear++;
q->item[q->rear] = t;
}
else
{
q->rear++;
q->item[q->rear] = t;
}
}
}
void delete(QUEUE *q)
{
if (isEmptyQueue(q))
{
printf("\n The Queue is Empty!");
}
else
{
if (q->front == q->rear)
{
initQueue(q);
}
else
{
q->front++;
}
}
}
TREE *peek(QUEUE *q)
{
TREE *t = NULL;
t = q->item[q->front];
return t;
}
TREE *create(TREE *t)
{
TREE *new_node, *temp;
QUEUE *q;
int i, n;
initQueue(q);
printf("\n Enter how many nodes:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->left = NULL;
new_node->right = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
insert(q, t);
}
else
{
temp = peek(q);
if (isEmpty(temp->left))
{
temp->left = new_node;
insert(q, temp->left);
}
else
{
if (isEmpty(temp->right))
{
temp->right = new_node;
insert(q, temp->right);
delete (q);
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
int isEmptyStack(STACK *s)
{
return (s->top == -1) ? 1 : 0;
}
int isFull(STACK *s)
{
return (s->top == MAX - 1) ? 1 : 0;
}
void push(STACK *s, TREE *n)
{
if (!isFull(s))
{
s->top++;
s->item[s->top] = n;
}
}
TREE *pop(STACK *s)
{
TREE *n;
if (!isEmptyStack(s))
{
n = s->item[s->top];
s->top--;
}
return n;
}
void inOrder(TREE *t)
{
TREE *temp;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
push(&s, temp);
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
printf("\t%d", temp->data);
temp = temp->right;
while (!isEmpty(temp))
{
push(&s, temp);
temp = temp->left;
}
}
}
int main()
{
int choice, n;
TREE *t = NULL;
do
{
printf("\n ---------------------");
printf("\n1.create\n2.display\n3.in-order\n4.Exit");
printf("\n ---------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
t = create(t);
break;
case 2:
printf("\n The Tree is:\n");
display(t);
break;
case 3:
printf("\n In-order traversal tree is:\n");
inOrder(t);
break;
}
} while (choice != 4);
getch();
return 0;
}
--------------------------------------------------------------------------------------
2) Write a C program to create binary search tree of integers and perform following operations: -
- Preorder traversal
- Postorder traversal.
ANS:
//Recursive functions....
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct tree
{
int data;
struct tree *left;
struct tree *right;
} TREE;
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
TREE *create(TREE *t)
{
int i, n;
TREE *new_node, *temp;
printf("Enter size of tree:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->left = NULL;
new_node->right = NULL;
printf("\nEnter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
if (temp->data <= new_node->data)
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
return t;
}
void display(TREE*t)
{
if(!isEmpty(t))
{
printf("\t%d",t->data);
display(t->left);
display(t->right);
}
}
void preOrder(TREE*t)
{
if(!isEmpty(t))
{
printf("\t%d",t->data);
preOrder(t->left);
preOrder(t->right);
}
}
void postOrder(TREE*t)
{
if(!isEmpty(t))
{
postOrder(t->left);
postOrder(t->right);
printf("\t%d",t->data);
}
}
int main()
{
int n,choice;
TREE*t=NULL;
do
{
printf("\n--------------");
printf("\n1.create\n2.display\n3.pre-order display\n4.post-order display\n5.Exit");
printf("\n--------------");
printf("\nEnter your choice:");;
scanf("%d",&choice);
switch (choice)
{
case 1:
t=create(t);
break;
case 2:
printf("\nThe Tree is:\n");
display(t);
break;
case 3:
printf("\nThe Pre-order tree is:\n");
preOrder(t);
break;
case 4:
printf("\nThe Post-order tree is:\n");
postOrder(t);
break;
}
} while (choice!=5);
getch();
return 0;
}
//Non-Recursive functions...
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
typedef struct tree
{
int data;
struct tree *left, *right;
} TREE;
typedef struct stack
{
TREE *data[MAX];
int top;
} STACK;
// function for stack empty or not
int isEmptyStack(STACK *s)
{
return (s->top == -1) ? 1 : 0;
}
// function for stack full or not
int isFullStack(STACK *s)
{
return (s->top == MAX - 1) ? 1 : 0;
}
// function for push into stack
void push(STACK *s, TREE *t)
{
if (isFullStack(s))
{
printf("\n The stack is full!");
}
else
{
s->top++;
s->data[s->top] = t;
}
}
// function for pop from stack
TREE *pop(STACK *s)
{
TREE *t = NULL;
if (isEmptyStack(s))
{
printf("\n The stack is Empty!");
}
else
{
t = s->data[s->top];
s->top--;
}
return t;
}
// Empty tree function
int isEmpty(TREE *t)
{
return (t == NULL) ? 1 : 0;
}
// creating binary search tree
TREE *create(TREE *t)
{
int i, n;
TREE *temp, *new_node;
printf("\n Enter size of tree:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
new_node = (TREE *)malloc(sizeof(TREE));
new_node->left = NULL;
new_node->right = NULL;
printf("\n Enter [%d] node data:", i);
scanf("%d", &new_node->data);
if (isEmpty(t))
{
t = new_node;
}
else
{
temp = t;
while (t)
{
if (temp->data > new_node->data)
{
if (isEmpty(temp->left))
{
temp->left = new_node;
break;
}
else
{
temp = temp->left;
}
}
else
{
if (temp->data <= new_node->data)
{
if (isEmpty(temp->right))
{
temp->right = new_node;
break;
}
else
{
temp = temp->right;
}
}
}
}
}
}
return t;
}
void display(TREE *t)
{
if (!isEmpty(t))
{
printf("\t%d", t->data);
display(t->left);
display(t->right);
}
}
void preOrder(TREE *t)
{
TREE *temp;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
printf("\t%d", temp->data);
push(&s, temp->right);
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
while (!isEmpty(temp))
{
printf("\t%d", temp->data);
push(&s,temp->right);
temp = temp->left;
}
}
}
void postOrder(TREE *t)
{
TREE *temp;
STACK s, s1;
s.top = s1.top = -1;
temp = t;
push(&s, temp);
while (!isEmptyStack(&s))
{
temp = pop(&s);
push(&s1, temp);
if (!isEmpty(temp->left))
{
push(&s, temp->left);
}
if (!isEmpty(temp->right))
{
push(&s, temp->right);
}
}
while (!isEmptyStack(&s1))
{
temp = pop(&s1);
printf("\t%d", temp->data);
}
}
void inOrder(TREE *t)
{
TREE *temp;
STACK s;
s.top = -1;
temp = t;
while (!isEmpty(temp))
{
push(&s, temp);
temp = temp->left;
}
while (!isEmptyStack(&s))
{
temp = pop(&s);
printf("\t%d", temp->data);
temp = temp->right;
while (!isEmpty(temp))
{
push(&s, temp);
temp = temp->left;
}
}
}
int main()
{
int choice, n;
TREE *t = NULL;
do
{
printf("\n-------------------");
printf("\n1.create\n2.display\n3.pre-order\n4.post-order\n5.in-order\n6.Exit");
printf("\n-------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
t = create(t);
break;
case 2:
printf("\n The Tree is:\n");
display(t);
break;
case 3:
preOrder(t);
break;
case 4:
postOrder(t);
break;
case 5:
inOrder(t);
break;
}
} while (choice != 6);
getch();
return 0;
}
------------------------------------------------------------------------------------------------------
Comments
Post a Comment
Enter comment here!