You cannot copy content of this page.

Monthly Archive October 2012

Program for representing multiple stacks in one array



Multiple Stacks in an array

Program for representing multiple stacks in one array

/*Implementing multiple stacks in a single array*/



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

#define MAX 10

void push(int,int[],int,int);
int pop(int,int[],int);
void display(int,int[],int);

/*array to top index for each stack*/
int t[MAX];
int top[MAX];

void main()
{
int arr[MAX],n,totstk,index;
int i,j,k=0,span,no,ch,num;
/*Input total elements of the array*/
/*This array may be divided into multiple stacks*/
printf(“nEnter size of the array?”);
scanf(“%d”,&n);

/*Input total stacks to be created in above array*/
printf(“nEnter total stacks to create?”);
scanf(“%d”,&totstk);

/*t[] array will contains totstk indexes for top*/
/*since total stacks to be created are totstk*/
/*Initializing t[] array with -1*/
for(i=0;i<totstk;i++)
t[i]=-1;

/*computes size of one stack*/
span=n/totstk;

/*store top of each stack in the array*/
/*this top serves as index for push/pop operations*/

top[k++]=0;
for(i=0;i<totstk-1;i++,k++)
top[k]=top[k-1]+span;

/*displaying elements of indexed array*/
for(i=0;i<totstk;i++)
printf(“%dt”,top[i]);
do{
clrscr();
printf(“nStacks-Menu (n stacks:1 array)”);
printf(“n1. Push”);
printf(“n2. Pop”);
printf(“n3. Display”);
printf(“n4. Quit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);

if(ch!=4)
{
printf(“nEnter stack number (0 to %d)?”,totstk-1);
scanf(“%d”,&index);
}

switch(ch)
{
case 1:
printf(“nEnter number to push?”);
scanf(“%d”,&no);
push(index,arr,span,no);
break;
case 2:
num=pop(index,arr,span);
printf(“nPopped element from stack %d is %d”,index,num);
break;
case 3:
display(index,arr,span);
break;
case 4:
exit(0);
}
getch();
}while(1);
}



void push(int index,int arr[],int n,int num)
{
int topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==topid+n-1)
{printf(“nStack Full! Overflow.”);
return;
}
topelement=++t[index];
arr[topid+topelement]=num;
}
int pop(int index,int arr[],int n)
{
int topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==-1)
{printf(“nStack Empty! Underflow.”);
return -1;
}
t[index]–;
return(arr[topid+topelement]);
}
void display(int index,int arr[],int n)
{
int i,topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==-1)
{printf(“nStack Empty! Underflow.”);
return;
}
for(i=topid+topelement;i>=topid;i–)
printf(“%dt”,arr[i]);
}


Tags, ,

Representing two stacks in an array



Stacks

Representing two stacks in an array

One array may be considered to be composed of multiple stacks, such that the size of the array is divided by the number of stacks to be created, which results in representing multiple stacks in one array.

For example:  If we wish to represent two stacks in one array of size 10, then the size of the array (10) may be divided by 2, to result in two stacks each of size 5.

Thus, when you push or pop an element, you must also state the stack id, along with other required information.



Tags,

Program to implement Stack using Linked List



Stacks

Program to implement Stack using Linked List:

/*Implementation of stacks using linked list*/

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

#define MAX 10

typedef struct stack
{
int info;
struct stack *next;
}stack;

/*create to allocate memory*/
stack *create()
{stack *temp = (stack *)malloc(sizeof(stack));
if(temp==NULL)
{printf(“nMemory allocation error!”);
exit(1);
}
return temp;
}

/*makenode to initialize new node*/
stack *makenode(int x)
{stack *temp=create();
temp->info=x;
temp->next=NULL;
return temp;
}

/*push to insert an element in list at beginning*/
stack *push(stack *top,int x)
{stack *temp;
stack *ptr=makenode(x);
if(top==NULL)
{top=ptr;
}
else
{ptr->next=top;
top=ptr;
}
}



/*pop to remove top element from stack*/

stack *pop(stack *top)
{stack *temp;
if(top==NULL)
{printf(“nStack Empty! Underflow.”);
return NULL;
}
printf(“nPopped element: %d”,top->info);
temp=top;
top=top->next;
free(temp);
return top;
}

/*displays contents of stack*/
void display(stack *top)
{
stack *temp;
if(top==NULL)
{printf(“nStack empty.”);
return;
}
temp=top;
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}



void main()
{
int ch,num;
stack *top=NULL;
while(1)
{
clrscr();
printf(“nStack-Menu”);
printf(“nn1. Push”);
printf(“n2. Pop”);
printf(“n3. Display”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter number to push?”);
scanf(“%d”,&num);
top=push(top,num);
break;
case 2:
top=pop(top);
break;
case 3:
display(top);
break;
case 4:
exit(0);
default:
printf(“nInvalid choice!”);
}
getch();
}
}


Tags,

Trees



Trees

Definitions:

Binary Tree:  A binary tree is either empty or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root.

Node:  Each element of a binary tree is called a node of a tree.

Father:  If A is the root of the binary tree and B is the root of its left or right subtree, then A is said to be the father of B and B is said to be the left or right son of A.

Child:  A node is a child node if it originates from a parent node.

Leaf:  A node that has no sons is called a leaf.  A leaf node is also called external node.

Internal Node:  The nodes, which have child nodes are called internal or interior nodes.

External Path Length:  The external path length of a binary tree is the sum of all the levels of all the external nodes of its extension.

Internal Path Length:  The internal path length of a binary tree is the sum of all the levels of all the internal nodes of its extension.

Ancestor:  Node n1 is an ancestor of node n2, if n1 is either the father of n2 or the father of some ancestor of n2.

Descendant:  Node n2 is a descendant of n1, if n2 is the left or right son or exists at any other lower level than n1.

Left Descendant:  A node n2 is a left descendant of node n1 if n2 is either the left son of n1 or a descendant of the left son of n1.

Right Descendant:  A node n2 is a right descendant of node n1 if n2 is either the right son of n1 or a descendant of the right son of n1.



Strictly Binary Tree:  If every non-leaf node in a binary tree has non-empty left and right subtrees, the tree is termed as Strictly binary tree.  A Strictly binary tree with n leaves always contains (2n-1) nodes.

Level of a node:

The root of the tree has level 0 and the level of any other node in the tree is one more than the level of its father.  Example: In the following tree, the level of G is 3, of D is 2 and of root, A is 0.

Depth of  a Tree:

The depth of a binary tree is the maximum level of any leaf in the tree.  This equals the length of the longest path from the root to any leaf.  Thus the depth of the above binary tree is 3.

Complete Binary Tree:

A Complete binary tree of depth d is the Strictly binary tree of all of whose leaves are at level d (eg. if depth is 2), the complete binary tree is:

NOTE:

1.  If a binary tree contains M nodes at level l, it contains at most 2m nodes at level l+1.

Example:  Let at level 1, number of nodes, m=2, then at level l+1 i.e. 1+1=2, nodes=2m=2*2=4.

2.  Since a binary tree can contain atmost one node at level 0 (the root), it can contain atmost one node 2L nodes at level L i.e. if level l is 3, then number of nodes = 2L =2 3 =8.  Thus at the most 8 nodes can be kept at level 3 in a CBT.

3.  A complete binary tree of depth d is the binary tree of depth d, that contains exactly 2L nodes at each level L, between 0 and d.

Let depth, d=2, L=2 {0,1,2}; nodes = {20,21,22} i.e. {1,2,4}.





Almost Complete Binary Tree:

A Binary tree of depth d is an almost complete binary tree, if:

  1. Any node nd at level less than (d-1) has two sons.
  2. For any node nd in the tree, with a right descendant at level d, nd must have a left descendant/son and every left descendant of nd is either a leaf at level d or has two sons.

(Numbering of nodes is done from left to right for the same level).

In the above example, depth =2

1.  node B at level 2-1 = 1 has 2 sons.

2.  At level 1, B has a right as well as a left descendant and C does not have left or right son.  Thus it is an example of an almost complete binary tree.

 

An almost complete strictly binary tree with n leaves has (2n-1) nodes as does any other strictly binary tree with n leaves.

An almost complete binary tree with n leaves that is not strictly binary has 2n nodes.
Binary Search Tree: 

A binary search tree is a binary tree that is either empty or in which each node contains a key that satisfies the conditions:

1.  All keys (if any) in the left subtree of the root precede the key in the root.

2.  The key in the root precedes all keys (if any) in its right subtree.

3.  The left and right subtrees of the root are again search trees.

 

Orchards, Trees and Binary Trees:

Tree:  It is any set of points (called vertices) and any set of pairs of distinct vertices (called edges or branches) such that-

(1) There is a sequence of edges (a path) from any vertex to any other; and

(2) There are no circuits, that is, no paths starting from a vertex and returning to the same vertex.

Such trees may be termed as Free Trees.  But the trees that we study are almost always tied up by having one particular vertex singled out as the root and for emphasis we call such a tree as a Rooted Tree. 

A rooted tree can be drawn in our usual way by picking it up by its root and shaking it so that all the branches and other vertices hand downward with the leaves at the bottom.  But there is no way to order nodes.

An Ordered Tree may be defined to be a rooted tree in which the children of each vertex are assigned an order.

2-Trees are rooted trees with the property that every vertex has either 0 or 2 children.

Forests and Orchards:  A forest is an arbitrary set of trees, where trees are sorted trees.  An orchard set of ordered trees is called forest or orchard.

We can build a rooted or an ordered tree by starting with a forest or an orchard attaching a new vertex at the top and adding branches from the new vertex (which will the the root) to the roots of all trees in the forest or the orchard.

Conversion of General Trees to a Binary Tree: 

To convert a general tree in to a binary tree, begin from root and join the nodes in left to right order for the same level that originate from the same root.  Remove all other links except left links and reconstruct the tree that will be a binary tree as follows:

Example:

Note: Arrow indicator shows the links to created for childs of same nodes at same level from left to right.  A hyphen (-) indicates the links to be deleted.

The binary tree for the above general tree is drawn below:

Conversion of an Orchard/Forest to Binary Tree:

Follow the same rule as applicable for conversion of a general tree to a binary tree.  The second general tree becomes the right child of the root of the first tree and so on.  The resultant tree is binary tree equivalent of a given forest or orchard.

 



Binary Tree Traversals:

Preorder (also known as Depth-first order)

  • Visit the root.
  • Traverse the left subtree in preorder.
  • Traverse the right subtree in preorder.

Inorder (or Symmetric order)

  • Traverse the left subtree in inorder.
  • Visit the root.
  • Traverse the right subtree in inorder.

Postorder (or End order)

  • Traverse the left subtree in postorder.
  • Traverse the right subtree in postorder.
  • Visit the root.

Expression Tree: 

An expression tree is build up from the simple operands and operators of an arithmetical or logical expression by placing the simple operands as the leaves of a binary tree and the operators as the interior nodes.  For each binary operator, the left subtree contains all the simple operands and operators in the left operand of the left operand of the given operator and the right subtree contains everything in the right operand.

For a unary operator, one subtree will be empty.

 



Polish Notations: Traversal of expression trees results in polish forms of expressions-

1. Traversal of an expression tree in preorder yields the prefix form of the expression, in which every operator is written before its operands.

2.  Inorder traversal gives the infix form.

3.  Postorder traversal gives the postfix form, in which all operators appear after their operands.

 

Tree Sort:  Inorder traversal of a tree yields sorted output, if it is a Binary Search Tree.  We may simple take the items to be sorted, build them into a binary search tree and use inorder traversal to put them in order.


Tags,

Threaded Binary Trees

Threaded Binary Trees

Threaded Binary Trees are an improvement over Binary Search Trees that uses stack for iterative traversal.  If a strategy is introduced such that the leaf node of a binary search tree points to its inorder predecessor or its successor, then direct links (called threads) are obtained to traverse a tree without using stack, which basically stores and retrieves the address of nodes in LIFO manner.  If the left pointer of the leaf node points to its inorder predecessor, then such a threaded tree is called Left-In-Threaded Binary Tree.  If the right pointer of the leaf node points to its inorder successor, then such a threaded tree is referred to as Right-In-Threaded Binary Tree. However, if both the links, left as well as right are available, then the threaded tree is called In-Threaded Binary Tree.

Threads are links or pointers that points to some node as per the sequence in inorder traversal (predecessor or successor).  It is required to differentiate a link from that of a thread, we may assume to integers lflag and rflag, which may take the value of 1 or 0.  If the value of lflag is 1 then it refers that the node contains a left thread, otherwise it is a link to the left subtree.  Moreover, leftmost pointer in an In-Threaded Binary Tree always points to NULL since no inorder  predecessor for the leftmost node is available.  This thread is referred to as dangling left thread.  Similar is the case with rightmost node, for which no inorder successor is available, and the thread so formed is called dangling right thread.

Function for Inorder Traversal of an In-Threaded Binary Tree: 

The basic advantage of Threaded Tree is that its inorder traversal does not require the use of stack.  Inorder traversal requires visiting the leftmost node, and then using right threads for the purpose of traversal.  The ‘C’ function for inorder traversal is given below:

/*Traverse in Inorder*/
void traverseInorder(tbt *root)
{tbt *temp=root;
while(temp->left)
temp=temp->left;
while(temp!=NULL)
{printf(“%dt”,temp->info);
if(temp->rflag==0)
{temp=temp->right;
while(temp->lflag==0)
temp=temp->left;
}
else
{temp=temp->right;
}
}
}

Function to insert a new node in In-Threaded Tree: 

Insertion of a new node in a Threaded tree is quite similar to that of insertion in a Binary Search Tree with the only difference that at each insertion step, the inorder predecessor and inorder successor of the new node must be set accordingly and the root of newnode must be set to bear a subtree rather than a thread.  The ‘C’ function to insert a new node in a Threaded Binary Tree is given below:

/*Insert a newnode in the threaded tree*/
tbt *insert(tbt *root,tbt *newnode)
{
tbt *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{
if(temp->left)
{if(temp->lflag==1)
{
newnode->left=temp->left;
newnode->right=temp;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{newnode->left=temp->left;
temp->left=newnode;
temp->lflag=0;
newnode->right=temp;
break;
}
}
else
{if(temp->right)
{if(temp->rflag==1)
{newnode->right=temp->right;
newnode->left=temp;
temp->right=newnode;
temp->rflag=0;
newnode->rflag=1;
break;
}
else
{temp=temp->right;
}
}
else
{
p=temp->right;
temp->right=newnode;
temp->rflag=0;
newnode->right=p;
newnode->left=temp;
break;
}
}
}
return root;
}

Function to find the Inorder Predecessor of a given node in an In-Threaded Binary Tree:  

Searching and returning inorder predecessor requires comparing each node with the value whose predecessor is required.  If the value is not found in the tree, error is reported.  If the value is found, then a temp pointer is placed on the left of this node and shifted until it points the rightmost node.  The value of the rightmost node is returned.  The ‘C’ function for returning Inorder predecessor of a given node is as follows:

/*Function that returns inorder predecessor*/
int inorderPredecessor(tbt *root,tbt *node)
{
int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{
if(temp->lflag==0)
temp=temp->left;
else /*move from left to right*/
temp=temp->right;
}
else if(node->info>temp->info)
{if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*if value is found*/
{if(temp->lflag==0)
{p=temp->left;
while(p->rflag!=1)
p=p->right;
num=p->info;/*predecssor*/
break;
}
else
{if(temp->left==NULL)
{num=0;
break;
}
else
{num=temp->left->info;
break;
}
}
}
}
return num;
}

Function to find the Inorder Successor of a given node in an In-Threaded Binary Tree: 

Searching and returning inorder successor requires comparing each node with the value whose successor is required.  If the value is not found in the tree, error is reported.  If the value is found, then a temp pointer is placed on the right of this node and shifted until it points the leftmost node.  The value of the leftmost node is returned.  The ‘C’ function for returning Inorder Successor of a given node is as follows:

/*Function that returns Inorder successor*/
int inorderSuccessor(tbt *root,tbt *node)
{int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{if(temp->lflag==0)
temp=temp->left;
else
temp=temp->right;
}
else if(node->info>temp->info)
{
if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*node->info==temp->info*/
{
if(temp->rflag==0)
{
p=temp->right;
while(p->lflag!=1)
p=p->left;
num=p->info;/*successor*/
break;
}
else
{
if(temp->right==NULL)
{num=0;
break;
}
else
{num=temp->right->info;
break;
}
}
}
}
return num;
}

Function to traverse a Left-In-Threaded Tree in Descending Order: 

Traversal of a Left In Threaded Tree result in a descending order of elements.  If the inorder traversal gives the result in Ascending order, then traversal using left threads may be performed such that the result is achieved in descending order.  The ‘C’ function for the same is as follows:

void traverseDescending(TBT *root)
{
TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->right;
}
printf(“%dt”,temp->info);
if((temp->lflag==1) && (temp->left==NULL))
return;
if(temp->lflag==1)
temp=temp->left;
else
p=temp->left;
}
}

 

Tags, ,

Program to implement In-Threaded Binary Tree

In-Threaded-Binary Tree

Program to implement In-Threaded Binary Tree:

/*In-threaded Binary Tree*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct threadedbinarytree
{
int info;
struct threadedbinarytree *left,*right;
int lflag,rflag;
}tbt;

tbt *create();
tbt *makenode(int);
tbt *insert(tbt *,tbt *);
int inorderSuccessor(tbt *,tbt *);
int inorderPredecessor(tbt *,tbt *);
void traverseInorder(tbt *);

/*Allocate memory*/
tbt *create()
{
tbt *temp=(tbt *)malloc(sizeof(tbt));
if(temp==NULL)
{printf(“nMemory Allocation Error!”);
exit(1);
}
return temp;
}

/*Make a new node*/
tbt *makenode(int x)
{
tbt *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->lflag=1; /*default is thread*/
temp->rflag=1;/*default is thread*/
return temp;
}

/*Insert a newnode in the threaded tree*/
tbt *insert(tbt *root,tbt *newnode)
{
tbt *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{
if(temp->left)
{if(temp->lflag==1)
{
newnode->left=temp->left;
newnode->right=temp;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{newnode->left=temp->left;
temp->left=newnode;
temp->lflag=0;
newnode->right=temp;
break;
}
}
else
{if(temp->right)
{if(temp->rflag==1)
{newnode->right=temp->right;
newnode->left=temp;
temp->right=newnode;
temp->rflag=0;
newnode->rflag=1;
break;
}
else
{temp=temp->right;
}
}
else
{
p=temp->right;
temp->right=newnode;
temp->rflag=0;
newnode->right=p;
newnode->left=temp;
break;
}
}
}
return root;
}

/*Function that returns Inorder successor*/
int inorderSuccessor(tbt *root,tbt *node)
{int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{if(temp->lflag==0)
temp=temp->left;
else
temp=temp->right;
}
else if(node->info>temp->info)
{
if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*node->info==temp->info*/
{
if(temp->rflag==0)
{
p=temp->right;
while(p->lflag!=1)
p=p->left;
num=p->info;/*successor*/
break;
}
else
{
if(temp->right==NULL)
{num=0;
break;
}
else
{num=temp->right->info;
break;
}
}
}
}
return num;
}

/*Function that returns inorder predecessor*/
int inorderPredecessor(tbt *root,tbt *node)
{
int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{
if(temp->lflag==0)
temp=temp->left;
else /*move from left to right*/
temp=temp->right;
}
else if(node->info>temp->info)
{if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*if value is found*/
{if(temp->lflag==0)
{p=temp->left;
while(p->rflag!=1)
p=p->right;
num=p->info;/*predecssor*/
break;
}
else
{if(temp->left==NULL)
{num=0;
break;
}
else
{num=temp->left->info;
break;
}
}
}
}
return num;
}

/*Traverse in Inorder*/
void traverseInorder(tbt *root)
{tbt *temp=root;
while(temp->left)
temp=temp->left;
while(temp!=NULL)
{printf(“%dt”,temp->info);
if(temp->rflag==0)
{temp=temp->right;
while(temp->lflag==0)
temp=temp->left;
}
else
{temp=temp->right;
}
}
}

void main()
{
int x,ch,num;
tbt *node, *root=NULL;
while(1)
{
clrscr();
printf(“nMenu-In Threaded Binary Tree”);
printf(“n1. Insert”);
printf(“n2. Inorder Traversal”);
printf(“n3. Return Inorder Predecessor”);
printf(“n4. Return Inorder Successor”);
printf(“n5. Exit”);
printf(“nnEnter your choice(1 to 5)?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter the number?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
traverseInorder(root);
break;
case 3:
printf(“nEnter the node whose predecessor is required?”);
scanf(“%d”,&num);
node=makenode(num);
x=inorderPredecessor(root,node);
if(x!=-1)
printf(“nInorder predecessor of %d is %d”,node->info,x);
else
printf(“nWrong node entered.”);
break;
case 4:
printf(“nEnter the node whose successor is required?”);
scanf(“%d”,&num);
node=makenode(num);
x=inorderSuccessor(root,node);
if(x!=-1)
printf(“nInorder successor of %d is %d”,node->info,x);
else
printf(“nWrong node entered.”);
break;
case 5:
exit(0);
default:
printf(“nInvalid Choice…!”);
}
getch();
}
}

Tags, ,

Program to implement Right-In-Threaded Binary Tree

Right-In-Threaded Binary Tree

Program to implement Right-In-Threaded Binary Tree:

/*Right In Threaded Binary Tree*/

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

typedef struct threadedbinarytree
{int info;
struct threadedbinarytree *left,*right;
int rlink;
}TBT;

TBT *create();
TBT *makenode(int);
TBT *insert(TBT *,TBT *);
/*inorder or symmetric order*/
void inorder(TBT *);
/*Depth first order*/
void preorder(TBT *);

TBT *create()
{
TBT *temp=(TBT *)malloc(sizeof(TBT));
if(temp==NULL)
{printf(“Memory Allocation Error!”);
exit(1);
}
return temp;
}

TBT *makenode(int x)
{TBT *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->rlink=1;/*1 for thread,0 for link*/
return temp;
}

TBT *insert(TBT *root,TBT *newnode)
{
TBT *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{if(temp->left)
temp=temp->left;
else
{temp->left=newnode;
newnode->left=NULL;
newnode->right=temp;
newnode->rlink=1; /*set during making node*/
break;
}
}
else
{if(temp->right)
{if(temp->rlink==1)
{
newnode->right=temp->right;
temp->right=newnode;
temp->rlink=0;
newnode->rlink=1;/*set during making node*/
break;
}
else
temp=temp->right;
}
else
{p=temp->right;
temp->right=newnode;
temp->rlink=0;
newnode->left=NULL;
newnode->right=p;
newnode->rlink=1;
break;
}
}
}
return root;
}

void preorder(TBT *root)
{TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
printf(“%dt”,p->info);
p=p->left;
}
if((temp->rlink==1)&&(temp->right==NULL))
return;
if(temp->rlink==1)
temp=temp->right->right;
else
temp=temp->right;
p=temp;
}
}

void inorder(TBT *root)
{TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->left;
}
printf(“%dt”,temp->info);
if((temp->rlink==1) && (temp->right==NULL))
return;
if(temp->rlink==1)
temp=temp->right;
else
p=temp->right;
}
}

void main()
{
int x,ch;
TBT *node,*root=NULL;
while(1)
{
clrscr();
printf(“nMenu- Right-in-Threaded Binary Tree”);
printf(“nn1. Insert”);
printf(“n2. Traverse inorder”);
printf(“n3. Traverse preorder”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number to insert?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
inorder(root);
break;
case 3:
preorder(root);
break;
case 4:
exit(0);
default:
printf(“nChoice is invalid.”);
}
getch();
}
}

Tags, ,

Program to implement Left-In-Threaded Binary Tree

Left-In-Threaded Binary Tree

Program to implement Left-In-Threaded Binary Tree:

/*Left In Threaded Binary Tree*/

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

typedef struct threadedbinarytree
{int info;
struct threadedbinarytree *left,*right;
int lflag;
}TBT;

TBT *create();
TBT *makenode(int);
TBT *insert(TBT *,TBT *);
void traverseDescending(TBT *);

TBT *create()
{
TBT *temp=(TBT *)malloc(sizeof(TBT));
if(temp==NULL)
{printf(“Memory Allocation Error!”);
exit(1);
}
return temp;
}

TBT *makenode(int x)
{TBT *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->lflag=1;/*1 for thread,0 for link*/
return temp;
}

TBT *insert(TBT *root,TBT *newnode)
{
TBT *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{if(temp->left)
{
if(temp->lflag==1)
{
newnode->left=temp->left;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{temp->left=newnode;
temp->lflag=0;
break;
}
}
else
{if(temp->right)
temp=temp->right;
else
{
temp->right=newnode;
newnode->left=temp;
newnode->lflag=1;
break;
}
}
}
return root;
}

void traverseDescending(TBT *root)
{
TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->right;
}
printf(“%dt”,temp->info);
if((temp->lflag==1) && (temp->left==NULL))
return;
if(temp->lflag==1)
temp=temp->left;
else
p=temp->left;
}
}

void main()
{
int x,ch;
TBT *node,*root=NULL;
while(1)
{
clrscr();
printf(“nMenu- Right-in-Threaded Binary Tree”);
printf(“nn1. Insert”);
printf(“n2. Traverse Descending Order”);
printf(“n3. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number to insert?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
traverseDescending(root);
break;
case 3:
exit(0);
default:
printf(“nChoice is invalid.”);
}
getch();
}
}

Tags, ,

Program to implement various operations on a Binary Search Tree

Binary Search Tree:

Program to implement various operations on Binary Search Tree:

/*Binary Search Tree*/

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

#define MAX 10

/* -OPERATIONS-
(i) Creation of a Binary Search Tree
(ii) Traversal
a) Preorder – Recursive/Iterative
b) Inorder – Recursive/Iterative
c) Postorder – Recursive/Iterative
d) Level by Level
(iii) Insertion
a) Recursive
b) Iterative
(iv) Deletion
a) Recursive
b) Iterative
(v) Searching
a) Recursive
b) Iterative
(vi) Finding Height
(vii) Finding number of nodes
{internal, external, total}
(viii) Finding number of leaves (external nodes)
(ix) Determining mirror image
(x) Creating clone
(xi) Sorting (Inorder traversal – Recursive)
(xii) Disposing
(xiii) Finding smallest – Recursive/Iterative
(xiv) Finding largest – Recursive/Iterative
*/

typedef struct binarysearchtree
{int info;
struct binarysearchtree *left;
struct binarysearchtree *right;
}BST;

/*Allocates the memory*/
BST *create();
/*Makes a new node*/
BST *makenode(int);
/*Inserts a new node in a BST using recursive definition*/
BST *insert(BST *,BST *);
/*Iteratively inserts a newnode in a BST*/
BST *iterativeinsert(BST *,BST *);
/*Traverses BST in preorder by recursive definition*/
void preorder(BST *);
/*Traverses BST in preorder by iterative definition*/
void iterativepreorder(BST *);
/*Traverses BST in inorder by recursive definition*/
void inorder(BST *);
/*Traverses BST in inorder using iterative definition*/
void iterativeinorder(BST *);
/*Traverses BST in postorder using recursive definition*/
void postorder(BST *);
/*Traverses BST in postorder using iterative definition*/
void iterativepostorder(BST *);
/*Searches a given element in BST recursively*/
void searchTree(BST *,int);
/*Searches a given element in BST iteratively*/
void iterativeSearchTree(BST *,int);
/*Returns largest from BST using recursive definition*/
int largest(BST *);
/*Returns largest value using iterative definition*/
int largestiterative(BST *);
/*Returns smallest value using recursive definition*/
int smallest(BST *);
/*Returns smallest value using iterative definition*/
int smallestiterative(BST *);
/*Generates mirror image of BST*/
void mirror(BST *);
/*Generates a duplicate copy of BST*/
void clone(BST *);
/*Returns total nodes of BST*/
int totalnodes(BST *);
/*Returns external nodes (leaf nodes) of BST*/
int external(BST *);
/*Returns internal nodes (interior nodes) of a BST*/
int internal(BST *);
/*Returns height of a BST*/
int heightTree(BST *);
/*Deletes a node from BST using recursive definition*/
BST *deletenode(BST *,int);
/*Deletes a node from BST using iterative definition*/
BST *deletenodeiterative(BST *,int);
/*Deletes BST completely using recursive definition*/
BST *dispose(BST *);
/*Delete BST completely using iterative definition*/
BST *iterativedispose(BST *);
/*Traverses BST level by level using recursive definition*/
void levelbyleveltraversal(BST *);
/*Traverses BST level by level using iterative definition*/
void iterativeleveltraversal(BST *);

/*Allocates the memory*/
BST *create()
{
BST *temp=(BST *) malloc(sizeof(BST));
if(temp==NULL)
{printf(“Memory Allocation Error.”);
exit(1);
}
return temp;
}

/*Makes a new node*/
BST *makenode(int x)
{BST *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
return temp;
}

/*Inserts a new node in a BST using recursive definition*/
BST *insert(BST *root,BST *num)
{if(root==NULL)
{root=num;
return root;
}
if(num->info < root->info)
root->left=insert(root->left,num);
else if(num->info > root->info)
root->right=insert(root->right,num);
else
printf(“nDuplicate Value…!”);
return root;
}

/*Iteratively inserts a newnode in a BST*/
BST *iterativeinsert(BST *root,BST *newnode)
{BST *p=root;
if(root==NULL)
{root=newnode;
return root;
}
while(p!=NULL)
{
if(newnode->info<p->info)
{if(p->left)
p=p->left;
else
{p->left=newnode;
break;
}
}
else if(newnode->info>p->info)
{if(p->right)
p=p->right;
else
{p->right=newnode;
break;
}
}
else
{printf(“nDuplicate key found…!”);
break;
}
}
return root;
}

/*Traverses BST in preorder by recursive definition*/
void preorder(BST *root)
{
if(root)
{printf(“%dt”,root->info);
preorder(root->left);
preorder(root->right);
}
}

/*Creating clone of a given tree*/
BST *newroot=NULL; /*global definition of root of new tree*/
void clone(BST *root)
{
BST *temp;
if(root)
{printf(“nMaking node %d”,root->info);
temp=makenode(root->info);
newroot=insert(newroot,temp);
clone(root->left);
clone(root->right);
}
}

/*Traverses BST in inorder by recursive definition*/
void inorder(BST *root)
{
if(root)
{inorder(root->left);
printf(“%dt”,root->info);
inorder(root->right);
}
}

/*Traverses BST in postorder using recursive definition*/
void postorder(BST *root)
{
if(root)
{postorder(root->left);
postorder(root->right);
printf(“%dt”,root->info);
}
}

/*Queue definition for Breadth first traversal*/

typedef struct queue
{int front,rear;
BST *arr[MAX];
}queue;

void enqueue(queue *q,BST *node)
{if(q->rear==MAX-1)
{printf(“nQueue Overflow…!”);
return;
}
q->arr[++q->rear]=node;
}

BST *dequeue(queue *q)
{if(q->rear==-1)
{printf(“nQueue underflow.”);
return NULL;
}
return(q->arr[q->front++]);
}

int empty(queue *q)
{return (q->front>q->rear);
}

void levelbyleveltraversal(BST *root)
{
queue q;
q.front=0;
q.rear=-1;
if(root!=NULL)
{enqueue(&q,root);
while(!empty(&q))
{
root=dequeue(&q);
printf(“%dt”,root->info);
if(root->left!=NULL)
enqueue(&q,root->left);
if(root->right!=NULL)
enqueue(&q,root->right);
}
}
}
/*Global stack declaration used for iterative traversals*/
typedef struct stack
{int top;
BST *items[MAX];
}stk;

/*Checks whether the stack is empty or not*/
int empty(stk *s)
{return(s->top==-1);
}

/*Push a node of BST into the stack*/
void push(stk *s, BST *t)
{if(s->top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
s->items[++(s->top)]=t;
}

/*Pops/returns a node of BST from the top of the stack*/
BST *pop(stk *s)
{if(s->top==-1)
{printf(“nStack Underflow…!”);
return NULL;
}
return(s->items[(s->top)–]);
}

/*Iterative Preorder Traversal*/
void iterativepreorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{
while(p!=NULL)
{printf(“%dt”,p->info);
push(&s,p);
p=p->left;
}
if(!empty(&s))
{p=pop(&s);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

/*Iterative Inorder Traversal*/
void iterativeinorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{while(p!=NULL)
{push(&s,p);
p=p->left;
}
if(!empty(&s))
{p=pop(&s);
printf(“%dt”,p->info);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

/*Global stack declarations used for
postorder iterative traversals*/

struct pstack
{BST *tree;
int visitedleft,visitedright;
}pstk[MAX];

/*Global declaration of top*/
int top=-1;

void ppush(struct pstack pstk[],BST *t,int VL,int VR)
{if(top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
top++;
pstk[top].tree = t;
pstk[top].visitedleft=VL;
pstk[top].visitedright=VR;
}

/*Pop the topmost element from the stack*/
struct pstack *ppop(struct pstack *pstk)
{struct pstack *temp;
if(top==-1)
{printf(“nStack Underflow…!”);
return NULL;
}
temp=&pstk[top];
top–;
return temp;
}

/*Checks & returns the value of top*/
int pempty()
{return(top==-1);
}

/*Iterative Postorder Traversal*/
void iterativepostorder(BST *root)
{
struct pstack *temp;
BST *p=root;
while(1)
{while(p!=NULL)
{ppush(pstk,p,1,0);
p=p->left;
}
if(pempty())
return;
temp=ppop(pstk);
if(temp->visitedleft==1 && temp->visitedright==1)
printf(“%dt”,temp->tree->info);
else
{ppush(pstk,temp->tree,temp->visitedleft,1);
p=temp->tree->right;
}
}
}

/*Searching a given node in a BST using recursive definition*/
void searchTree(BST *root,int num)
{if(root==NULL)
{printf(“Number not found…!”);
return;
}
if(num<root->info)
searchTree(root->left,num);
else if(num>root->info)
searchTree(root->right,num);
else
{printf(“nNumber is found…!”);
return;
}
}

/*Searching a given node in a BST using Iterative definition*/
void iterativeSearchTree(BST *root,int num)
{BST *p=root;
if(root==NULL)
{printf(“nNumber not found…!”);
return;
}
while(p!=NULL)
{if(num<root->info)
{if(root->left)
root=root->left;
else
{printf(“nNumber not found…!”);
return;
}
}
else if(num>root->info)
{if(root->right)
root=root->right;
else
{printf(“nNumber not found…!”);
return;
}
}
else
{printf(“nNumber found…!”);
return;
}
}
return;
}

/*Return largest value from BST.
Iterative Definition*/
int largest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->right!=NULL)
p=p->right;
return(p->info);
}

/*Return smallest value from BST.
Iterative Definition*/
int smallest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->left!=NULL)
p=p->left;
return(p->info);
}

/*Return largest value from BST using recursive definition*/
int largestiterative(BST *root)
{if(root==NULL)
return -1;
if(root->right==NULL)
return(root->info);
else
return largestiterative(root->right);
}

/*Return smallest value from BST using recursive definition*/
int smallestiterative(BST *root)
{if(root==NULL)
return -1;
if(root->left==NULL)
return(root->info);
else
return smallestiterative(root->left);
}

/*Generating mirror image*/
void mirror(BST *root)
{BST *temp;
if(root)
{mirror(root->left);
mirror(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;
}
}

/*Return total nodes of a BST*/
int totalnodes(BST *root)
{if(root==NULL)
return 0;
else
return(totalnodes(root->left)+totalnodes(root->right)+1);
}

/*Return external/leaf nodes of a BST*/
int external(BST *root)
{if(root==NULL)
return 0;
else if(root->left==NULL && root->right==NULL)
return 1;
else
return(external(root->left)+external(root->right));
}

/*Return internal/interior nodes of a BST*/
int internal(BST *root)
{if((root==NULL) || ((root->left==NULL)&&(root->right==NULL)))
return 0;
else
return(internal(root->left)+internal(root->right)+1);
}

/*Return height of a tree – recursive definition*/
void heightTree(BST *root,int *height)
{int leftsubtree,rightsubtree;
if(root==NULL)
{*height=0;
}
else
{heightTree(root->left,&leftsubtree);
heightTree(root->right,&rightsubtree);
if(leftsubtree>rightsubtree)
*height=leftsubtree + 1;
else
*height=rightsubtree + 1;
}
}

/*Returns degree of a given node*/
int degree(BST *root)
{if(root->left==NULL && root->right==NULL)
return 0;
else if(root->left!=NULL && root->right!=NULL)
return 2;
else
return 1;
}

/*Deletion of a node from BST using recursive definition*/
BST *deletenode(BST *root,int val)
{BST *temp;
if(root==NULL)
return root;
if(val<root->info)
root->left=deletenode(root->left,val);
else if(val>root->info)
root->right=deletenode(root->right,val);
else /*if only one node exists*/
{if(degree(root)==0)
{free(root);
return NULL;
}
/*if node contains one child either left or right*/
if(degree(root)==1)
{
if(root->right)
{temp=root->right;
free(root);
return temp;
}
else
{temp=root->left;
free(root);
return temp;
}
}
/*If node to be deleted contains both
left as well as right child*/
if(degree(root)==2)
{temp=root->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=root->left;
temp=root->right;
free(root);
return temp;
}
}
return root;
}

/*Deletion of a node from BST using iterative definition*/
BST *deletenodeiterative(BST *root,int val)
{
BST *cur,*prev,*temp;
if(root==NULL)
return root;
cur=root;
prev=NULL;
while(cur!=NULL && cur->info!=val)
{prev=cur;
if(val<cur->info)
cur=cur->left;
else
cur=cur->right;
}
if(cur==NULL)
return root;
if(degree(cur)==0)
{
if(prev) /*not a root node*/
{
if(prev->left==cur)
prev->left=NULL;
else
prev->right=NULL;
free(cur);
}
else
{free(cur);
return NULL;
}
}
else if(degree(cur)==1)
{if(cur->left)
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->left;
else
prev->right=cur->left;
free(cur);
}
else{
prev=cur->left;
free(cur);
return(prev);
}
}
else
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->right;
else
prev->right=cur->right;
free(cur);
}
else
{
prev=cur->right;
free(cur);
return (prev);
}
}
}
else if(degree(cur)==2)
{if(prev->left==cur)/*case I*/
/*then traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
prev->left=cur->right;
free(cur);
}
else/*case II*/
/*traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
if(prev!=NULL)
prev->right=cur->right;
temp=cur->right;
free(cur);
return temp;
}
}
return root;
}

/*function to dispose the BST*/
BST *dispose(BST *root)
{BST *left,*right;
if(root!=NULL)
{left=root->left;
right=root->right;
free(root);
root=dispose(left);
root=dispose(right);
}
return root;
}

void main()
{
int ch,x,flag=0;
BST *newnode,*root=NULL;
while(1)
{clrscr();flag=0;
printf(“nMenu-Binary Search Tree Operations”);
printf(“nn1. Recursive”);
printf(“n2. Non-Recursive”);
printf(“n3. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
do
{
clrscr();
printf(“nnRecursive Menu”);
printf(“nn1. Insertion”);
printf(“n2. Inorder traversal”);
printf(“n3. Preorder traversal”);
printf(“n4. Postorder traversal”);
printf(“n5. Deletion”);
printf(“n6. Search node”);
printf(“n7. Find height”);
printf(“n8. Find total nodes”);
printf(“n9. Find leaf nodes”);
printf(“n10. Find interior nodes”);
printf(“n11. Generate mirror image”);
printf(“n12. Generate clone”);
printf(“n13. Display sorted order”);
printf(“n14. Dispose tree”);
printf(“n15. Find largest node”);
printf(“n16. Find smallest node”);
printf(“n17. Return”);

printf(“nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter the number?”);
scanf(“%d”,&x);
newnode=makenode(x);
root=insert(root,newnode);
break;
case 2: inorder(root);
break;
case 3: preorder(root);
break;
case 4: postorder(root);
break;
case 5: printf(“nEnter the node to delete?”);
scanf(“%d”,&x);
root=deletenode(root,x);
break;
case 6: printf(“nEnter the number to search?”);
scanf(“%d”,&x);
searchTree(root,x);
break;
case 7: heightTree(root,&x);
printf(“nHeight = %d”,x);
break;
case 8: x=totalnodes(root);
printf(“nTotal nodes = %d”,x);
break;
case 9:x=external(root);
printf(“nLeaf nodes = %d”,x);
break;
case 10:x=internal(root);
printf(“nInterior Nodes = %d”,x);
break;
case 11:mirror(root);
break;
case 12:clone(root);
printf(“nDisplaying original BST-inorder”);
inorder(root);
printf(“nDisplaying its clone-inorder”);
inorder(newroot);
break;
case 13:printf(“nTree elements in sorted order:”);
inorder(root);
break;
case 14:printf(“nDisposing the tree…!”);
root=dispose(root);
break;
case 15:x=largest(root);
printf(“nLargest value = %d”,x);
break;
case 16:x=smallest(root);
printf(“nSmallest value = %d”,x);
break;
case 17:flag=1;break;
default:printf(“nInvalid choice…!”);
}
getch();
}while(flag!=1);
break;
case 2:
do
{clrscr();
printf(“nnNon-Recursive/Iterative Menu”);
printf(“n1. Insertion”);
printf(“n2. Inorder traversal”);
printf(“n3. Preorder traversal”);
printf(“n4. Postorder traversal”);
printf(“n5. Level by level/BFS traversal”);
printf(“n6. Deletion”);
printf(“n7. Search node”);
printf(“n8. Find largest node”);
printf(“n9. Find smallest node”);
printf(“n10. Return”);
printf(“nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{case 1: printf(“nEnter the number?”);
scanf(“%d”,&x);
newnode=makenode(x);
root=iterativeinsert(root,newnode);
break;
case 2: iterativeinorder(root);
break;
case 3: iterativepreorder(root);
break;
case 4: iterativepostorder(root);
break;
case 5: levelbyleveltraversal(root);
break;
case 6: printf(“nEnter the node to delete?”);
scanf(“%d”,&x);
root=deletenodeiterative(root,x);
break;
case 7: printf(“nEnter the number to search?”);
scanf(“%d”,&x);
iterativeSearchTree(root,x);
break;
case 8:x=largestiterative(root);
printf(“nLargest value = %d”,x);
break;
case 9:x=smallestiterative(root);
printf(“nSmallest value = %d”,x);
break;
case 10:flag=1;break;
default:printf(“nInvalid choice…”);
}
getch();
}while(flag!=1);
break;
case 3:
exit(0);
default:
printf(“nInvalid choice…!”);
}
}
}

Tags, ,

Program to create a Binary Search Tree

Binary Search Trees: 

A Binary Search Tree is a Binary Tree which satisfies the following conditions:

  1. The left subtree of the root contains keys smaller than the root.
  2. The right subtree of the root contains keys greater than the root.
  3. The left and right subtrees are also Binary Search Trees.
  4. There are no duplicates in the tree.

Program to create a Binary Search Tree:

/*Creating a Binary Search Tree*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct binarytree
{int info;
struct binarytree *left;
struct binarytree *right;
}BT;

BT *create()
{BT *temp=(BT *)malloc(sizeof(BT));
if(temp==NULL)
{printf(“nMemory Allocation Error.”);
exit(1);
}
return temp;
}

BT *makenode(int x)
{BT *ptr=create();
ptr->info=x;
ptr->left=NULL;
ptr->right=NULL;
return ptr;
}

BT *insert(BT *root,int x)
{BT *p,*q,*ptr=makenode(x);
if(root==NULL)
{root=ptr;
return root;
}
p=q=root;
while(p!=NULL)
{q=p;
if(x<q->info)
p=q->left;
else
p=q->right;
}
if(x<q->info)
q->left=ptr;
else
q->right=ptr;
return root;
}

void inorder(BT *root)
{if(root)
{inorder(root->left);
printf(“%dt”,root->info);
inorder(root->right);
}
}

void preorder(BT *root)
{if(root)
{printf(“%dt”,root->info);
preorder(root->left);
preorder(root->right);
}
}

void postorder(BT *root)
{if(root)
{postorder(root->left);
postorder(root->right);
printf(“%dt”,root->info); }
}

void main()
{
BT *root=NULL;
int ch,x;
while(1)
{clrscr();
printf(“nBinary Search Tree-MENU”);
printf(“nn1. Insert Node”);
printf(“n2. Inorder Display”);
printf(“n3. Preorder Display”);
printf(“n4. Postorder Display”);
printf(“n5. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter number?”);
scanf(“%d”,&x);
root=insert(root,x);
break;
case 2:
inorder(root);
break;
case 3:
preorder(root);
break;
case 4:
postorder(root);
break;
case 5:
exit(0);
default:
printf(“nInvalid Choice.”);
}
getch();
}
}

 

Tags, ,

x Close

Like Us On Facebook