Write a C program to copy one linked list to another and count the number of node

 # include <stdio.h>
# include <stdlib.h>
struct list
{
char info[20];
struct list *next;
struct list *prev;
};
struct list *new1,*node;
void create(struct list *s,struct list *e)
{
char ch;
node=s;
printf("\nWant to create a node(y/n):");
ch=getche();
while (ch != 'n')
{
node->next = (struct list *) malloc(sizeof(struct list));
node->next->prev= node;
node = node->next;
printf("\n Enter the string value:- ");
gets(node->info);
node->next = e;
e->prev=node;
printf("\n Enter choice--'n' for break: ");
ch = getche();
}
}
void displayL (struct list *s,struct list *e)
{
node = s->next;
while (node!=e)
{
printf(" %u--%s", node,node->info);
node = node->next;
}
printf("\n");
}
void displayR (struct list *e,struct list *s)
{
node = e->prev;
while (node!=s)
{
printf("  %s",node->info);
node = node->prev;
}
printf("\n");
}
void merge(struct list *s,struct list *e, struct list *s1,struct list *e1)
{
int i=0;
s=s->next;

while(s!=e)
{
s1->next=(struct list*)malloc(sizeof(struct list));
s1->next->prev=s1;
s1=s1->next;
 strcpy(s1->info,s->info);
 s=s->next;
 s1->next=e1;
e1->prev=s1;

 i++;
}
printf("\nNumber of Nodes: %d",i);
}
void main()
{
struct list *start,*end,*start1,*end1;
clrscr();
start= (struct list *) malloc(sizeof(struct list));
start->next=NULL;
end= (struct list *) malloc(sizeof(struct list));
end->next=NULL;
start1= (struct list *) malloc(sizeof(struct list));
start1->next=NULL;
end1= (struct list *) malloc(sizeof(struct list));
end1->next=NULL;
create(start,end);
printf("\n Created list is as follows(L ->R)\n");
displayL(start,end);
printf("\n Created list displayed from R->L\n");
displayR(end,start);
merge(start,end,start1,end1);
printf("\n Copied List from L ->R\n");
displayL(start1,end1);
printf("\n list from R to L after deletion\n");
displayR(end1,start1);

getch();

}

Deletion Of All Nodes From A Doubly Linked List

 
# include < stdio.h>
# include < stdlib.h>
struct link
{
char info[20];
struct link *next;
};
struct link *start,*p,*node;
int i=1;
void create()
{
char ch='y';
node=start;
while(ch != 'n')
{
node->next = (struct link* ) malloc(sizeof(struct link));
node = node->next;
printf("\n Enter string for node: %d: ",i);
scanf("%s", node->info);
node->next = NULL;
i++;
printf("\n Enter choice-- 'n' for break: ");
ch = getche();
}
}
void display(struct link *n)
{
node=n;
while(node)
{
printf("\n 0x%x ", node);
printf("%s\n",node->info);
node=node->next;
}
}
void delNodes(struct link *n)
{
node=n;
p = n->next;

while(p)
{

node->next = p->next;
printf("Deleting %s\n",p->info);
free(p);
p = node->next;
}
do
{
free(start);
start=start->next;
}while(start);
}

void main()
{
clrscr();
start = (struct link* ) malloc(sizeof(struct link));
printf("\n Enter string for node: %d: ",i);
scanf("%s", start->info);
start->next = NULL;
create();
printf("\nAfter Creation...");
display(start);
delNodes(start);
printf("\nAfter Deletion...");
display(start);
getch();

}

C function to delete odd position elements from doubly linked list

 
# include < stdio.h>
# include < stdio.h>
struct list
{
int age;
struct list *next;
struct list *prev;
};
struct list *new1,*node;
void create(struct list *s,struct list *e)
{
char ch;
node=s;
node->next = (struct list *) malloc(sizeof(struct list));
node->next->prev= node;
node = node->next;
node->next=e;
e->prev=node;
printf("\n Enter the numeric value:- ");
scanf("%d",&node->age);

printf("\nWant to create a node(y/n):");
ch=getche();
while (ch != 'n')
{
node->next = (struct list *) malloc(sizeof(struct list));
node->next->prev= node;
node = node->next;
printf("\n Enter the numeric value:- ");
scanf("%d",&node->age);
printf("\n Enter choice--'n' for break: ");
ch = getche();
}
node->next = e;
e->prev=node;

}
void displayL (struct list *s,struct list *e)
{
node = s->next;
while (node!=e)
{
printf("\n%d", node->age);
node = node->next;
}
printf("\n");
}
void displayR (struct list *e,struct list *s)
{
node = e->prev;
while (node!=s)
{
printf("\n%d",node->age);
node = node->prev;
}
printf("\n");
}
void delA(struct list *s,struct list *e)
{
int c=1,counter;
printf("\nEnter the location of the node to be deleted:");
scanf("%d",&counter);
node=s->next;
while(node->next!=e)
{
if(c==counter)
break;
c++;
node=node->next;
}
node->prev->next=node->next;
node->next->prev=node->prev;
free(node);
}
void main()
{
struct list *start,*end;
clrscr();
start=(struct list *) malloc(sizeof(struct list));
end=(struct list *) malloc(sizeof(struct list));
create(start,end);
printf("\n Created list is as follows(L ->R)\n");
displayL(start,end);
printf("\n Created list displayed from R->L\n");
displayR(end,start);
printf("\nDeleting the First node\n");
delA(start,end);
printf("\n now the listfrom L ->R\n");
displayL(start,end);
printf("\n list from R to L after deletion\n");
displayR(end,start);
getch();

}

Searching program on tree using C Language

The following program will store names in a tree and then search a name , entered by the user in the tree.

# include< stdio.h>

# include< stdlib.h>

#include< string.h>

struct node

{

char info[100];

struct node *left;

struct node *right;

};

int flag=0;

int search(struct node *n, char info[100])

{

while (n != NULL)

{

if (strcmp(n->info,info)==0)

{

flag = ++;

}

else

{

if(strcmp(info,n->info)<=0)

n = n->left;

else

n = n->right;

}

}

return(flag);

}

struct node * create()

{

 struct node *node;

 char info[100];

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

 fflush(stdin);

 printf("\nEnter the name:-");

 gets(info);

 strcpy(info,strupr(info));

strcpy(node->info,info);

 node->left=NULL;

 node->right=NULL;

 return node;

}

struct node *add(struct node *t,struct node *root)

{

if(root==NULL)

{

 root=t;

 return root;

 }

if(strcmp(t->info,root->info)<=0)

root->left=add(t,root->left);

else

root->right=add(t,root->right);

return root;

}

void  output(struct node *t, int level)

{

int i;

if (t)

{

 output(t->right, level+1);

 printf("\n");

for (i = 0; i < level; i++)

printf("   ");

printf("%s,%d (level)", t->info,level);

printf("\n");

 output(t->left, level+1);

}

}

void main()

{

int flag,xx=0;

char info[100];

char choice='y';

struct node *t,*root=NULL,*rr;

clrscr();

while(choice != 'n')

{

t=create ();

if(xx==0)

rr=t;

xx++;

printf("\n Tree is ");

root=add(t,root);

output(rr,0);

fflush(stdin);

printf("\n Enter choice--'n' to break:");

scanf("%c",&choice);

fflush(stdin);

}

printf("\nEnter the value to be searched :-");

gets(info);

strcpy(info,strupr(info));

flag = search(rr,info);

if (flag)

printf("\n Element is available in the tree. \n");

else

printf("Element is not avaible in the tree.");

getch();

}

C Data Structure Program on Searching a tree

A common action involving trees is a search for values in a tree.One of the advantages of tree over  linked list is that you can determine whether an element is in a tree in fewer steps than you need to search for an element in a linked list.

# include< stdio.h>

# include< stdlibc.h>

struct node

{

int info;

struct node *left;

struct node *right;

};

int i=0,j=0,flag=0,x=0,y=0;

int search(struct node *n, int info)

{

while (n != NULL)

{

if (n->info == info)

{

flag = 1;

return(flag);

}

else

{

if(info < n->info)

n = n->left;

else

n = n->right;

}

}

return(flag);

}

struct node * create()

{

  struct node *node;

  int info;

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

  fflush(stdin);

  printf("\nEnter the value:-");

  scanf("%d",&info);

  node->info=info;

  node->left=NULL;

  node->right=NULL;

  return node;

}

struct node *add(struct node *t,struct node *root)

{

 if(root==NULL)

   {

   root=t;

   return root;

   }

   if(t->info<=root->info)

      root->left=add(t,root->left);

   else

    root->right=add(t,root->right);

     return root;

 }

void  output(struct node *t, int level)

{

int i;

if (t)

{

 output(t->right, level+1);

  printf("\n");

for (i = 0; i < level; i++)

printf("   ");

printf("%d,%d (level)", t->info,level);

printf("\n");

 output(t->left, level+1);

}

}

void main()

{

int flag, info, xx=0;

char choice='y';

struct node *t,*root=NULL,*rr;

clrscr();

 while(choice != 'n')

{

 t=create ();

if(xx==0)

 rr=t;

xx++;

printf("\n Tree is ");

root=add(t,root);

output(rr,0);

fflush(stdin);

printf("\n Enter choice--'n' to break:");

scanf("%c",&choice);

}

printf("\nEnter the value to be searched :-");

scanf("%d",&info);

flag = search(rr, info);

if (flag)

printf("\n Element is available in the tree. \n");

else

printf("Element is not avaible in the tree.");

getch();

}

C Program on traversing binary tree

Once you have created a binary tree , you can display it’s contents in several ways. The process of moving through a tree is known as tree traversal. The traversal of a binary tree involves visiting each node in the tree exactly once. There are three popular methods of  binary tree traversal – inorder , preorder and post order traversal . Traversing a binary tree means visiting the root node , it’s left and right sub trees. The only difference among the methods is the order in which these three operations are performed.

To traverse a binary tree in in order , we perform the following operations :-

      1.Traverse the left sub tree in order

      2.Visit the root.

      3.Traverse the right sub tree in order.

To traverse a tree in pre order

      1.Visit the root.

      2.Traverse the left sub tree in pre order

      3.Traverse the right sub tree in pre order

To traverse a tree in post order

      1.Traverse the left sub tree in post order

      2.Traverse the right sub tree in post order

      3.Visit the root.

For example consider a tree whose nodes can contain operators and operands.

The postorder traversal of the tree gives the postfix form of the expression :- 78+

The preorder traversal of the tree gives the prefix form of the expression :-    +78

The inorder traversal of the tree gives the infix form of the expression :-        7+8

The following diagram represents a binary tree with 8 nodes  and we will see how this tree can be traversed in inorder, preorder and postorder methods.

  

Firstly we will see how this tree will be traversed in preorder method.In preorder root is traversed first, then the left subtree in preorder style and lastly the right subtree in preorder style.So the traverse will be

s (root , after this traversing through the left branch starts)à d (root )àa (left)àe (right)à (main left branch ends here , so traversing through the main right branch starts from here ) t (root)ày(no left node, so right branch)à u (left)à z ( right)  [ s d a e t y u z ]

In case of inorder method , left subtree is traversed first in inorder method , then the root and lastly the right subtree in inorder method.So the traverse will be like : a (left node of left subtree) àd (root) àe (right ) às ( left subtree ends here , so the root) à t ( no left node , so the root) àu (left )ày (root)àz (right) [a  d  e  s  t  u  y  z]

In case of postorder method , the style is left , right , root in postorder method. So if the above binary tree is traversed in postorder method then traverse will be like : a à e à d à (left subtree ends here , now traversing through right subtree will start) à u  à  z à y à t  à s  [ a  e  d  u  z  y  t  s ]

The C Program on traversal of a tree

# include< stdio.h>

# include< stdlib.h>

#include< conio.h>

struct node

{

char info;

struct node *left;

struct node *right;

};

void pre_order (struct node *n)

{

if (n)

{

printf(" %c", n->info);

pre_order(n->left);

pre_order(n->right);

}

}

void in_order (struct node *n)

{

if (n)

{

in_order(n->left);

printf(" %c", n->info);

in_order(n->right);

}

}

void post_order (struct node *n)

{

if (n)

{

post_order(n->left);

post_order(n->right);

printf(" %c", n->info);

}

}

struct node * create()

{

 struct node *node;

 char x;

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

 printf("\nEnter the value:-");

 scanf("%c",&x);

 node->info=x;

 node->left=NULL;

 node->right=NULL;

 return node;

}

struct node *add(struct node *t,struct node *root)

{

if(root==NULL)

{

root=t;

return root;

}

else

{

if(t->info<=root->info)

{

root->left=add(t,root->left);

printf("\nAdded to left of node %c",root->info);

 }

else

{

 root->right=add(t,root->right);

 printf("\nAdded to right of node %c",root->info);

 }

 return root;

}

}

void  output(struct node *t, int level)

{

int i;

if (t)

{

output(t->right, level+1);

printf("\n");

for (i = 0; i < level; i++)

printf("   ");

printf("%c,%d (level)", t->info,level);

printf("\n");

 output(t->left, level+1);

}

}

void main()

{

int info, xx=0;

char choice='y';

struct node *t,*root=NULL,*rr;

clrscr();

while(choice != 'n')

{

t=create ();

 if(xx==0)

 rr=t;

xx++;

printf("\n Tree is ");

root=add(t,root);

output(rr,0);

fflush(stdin);

printf("\n Enter choice--'n' to break:");

scanf("%c",&choice);

}

printf("\n Pre-order traversal\n");

pre_order (rr);

printf("\n In-order traversal\n");

in_order (rr);

printf("\n Post-order traversal\n");

post_order (rr);

getch();

}

C Program to calculate depth of a tree

To following program will calculate the depth of a tree:-

# include< stdio.h>

# include< stdlib.h>

#include< conio.h>

struct node

{

int info;

struct node *left;

struct node *right;

};

int d=0;

int depth (struct node *n, int level)

{

if (n != NULL)

{

if (level > d)

d = level;

depth (n->left,level + 1);

depth (n->right,level + 1);

}

return (d);

}

struct node * create()

{

  struct node *node;

  int x;

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

  printf("\nEnter the value:-");

  scanf("%d",&x);

  node->info=x;

   node->left=NULL;

  node->right=NULL;

  return node;

}

struct node *add(struct node *t,struct node *root)

{

 if(root==NULL)

{

  root=t;

  return root;

}

else

{

if(t->info<=root->info)

{

 root->left=add(t,root->left);

 printf("\nAdded to left of node %d",root->info);

 }

else

{

root->right=add(t,root->right);

printf("\nAdded to right of node %d",root->info);

}

 return root;

}

}

void  output(struct node *t, int level)

{

int i;

if (t)

{

output(t->right, level+1);

printf("\n");

for (i = 0; i < level; i++)

printf("   ");

printf("%d,%d (level)", t->info,level);

printf("\n");

 output(t->left, level+1);

}

}

void main()

{

int info,d,xx=0;

char choice='y';

struct node *t,*root=NULL,*rr;

clrscr();

 while(choice != 'n')

{

 t=create ();

 if(xx==0)

 rr=t;

xx++;

printf("\n Tree is ");

root=add(t,root);

output(rr,0);

fflush(stdin);

printf("\n Enter choice--'n' to break:");

scanf("%c",&choice);

}

d = depth(rr, 0);

printf("\n Depth of the above tree is:  %d", d);

getch();

Binary Tree in C Data Structure

We have already seen several data structures  like linked list , stack and queue.In linked list we have seen that method of traversing the list , from one node to the other.Let us see a better way of doing the same thing using Tree.Like linked lists, trees are made of nodes which contains both information part and address pointers.In linked list , an address pointer of a node holds the address of just another node, while in tree the address pointers can hold the address of more than one node of the same type.

A binary tree can thus be defined as a finite set of elements that is either empty or is partitioned into three disjoint subsets.The first subset contains a single element called the root of the tree.The other subsets are themselves binary trees , called the left and right subtree of the original tree.So while adding elements into a tree , we can add them category wise in left and right subfreezing case of searching the values , it will take less time.

                                                                                                             

A, B, C, D, E, F, G and I are all nodes. If A is the root of the binary tree then B is the root of the left sub tree and C is the root of right subtree.A is said to be the father of B and C while B is said to be the left son of A and C is said to be the right son of A. If a node doesn’t have any son then the node is called a leaf. Here D, G, H and I are leafs. The absence of a branch indicates an empty subtree.Here in the above diagram E and C are empty subtree.Two nodes are called brother is they are left and right son of the same father. In binary tree root is at the top and the leafs are at the bottom. So traversing from the leafs to the root is called climbing the tree and the reverse is called descending the tree. If every nonlife node in a binary tree has nonempty left and right sub tree then it is called a strictly binary tree. The above diagram is not a strictly binary tree.

The root of a tree has level 0 and the level of any other node in a tree is one more than the level of its father. The depth of a binary tree is the maximum level of a leaf in the tree. This equals to the longest path from the root to the leaf. A strictly binary tree is called a complete binary treewhen all the leafs of the tree have the same depth.

Now we will create a tree of linked list in such a manner that the nodes of the linked list will have one information part and two address pointers. In the info part numeric value will be stored while one address pointer will point to the right branch of the tree and the other will point to the left branch of the tree. The first value will be the root of the tree. After that whenever a value is read it will be compared with the contents of the tree (starting from root) and a left branch will be created if the value is found less than or equal to the content of a node otherwise the value will be inserted in the right branch.

# include< stdio.h>

# include< stdlib.h>

#include< conio.h>

struct node

{

int info;

struct node *left;

struct node *right;

};

struct node * create()

{

  struct node *node;

  int x;

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

  printf("\nEnter the value:-");

  scanf("%d",&x);

  node->info=x;

   node->left=NULL;

  node->right=NULL;

  return node;

}

/*The above function creates a node for the tree and set value in the node */

struct node *add(struct node *t,struct node *root)

{

 if(root==NULL)

{

  root=t;

  return root;

}

else

{

if(t->info<=root->info)

{

 root->left=add(t,root->left);

 printf("\nAdded to left of node %d",root->info);

 }

else

{

root->right=add(t,root->right);

printf("\nAdded to right of node %d",root->info);

}

 return root;

}

}

/* Function add () adds the current created node in the specified location of the tree. If the tree passed as a parameter ( here root ) is empty , the current node is added ( here t ) and becomes the root of the tree. Otherwise , the program decides whether to continue it’s search down the left or the right sub tree. If the data member of the new node is less than or equal to the root node value then the function will continue along the left sub tree , otherwise the search continues along the right sub tree. If the searching process needs to be continued , the function calls itself with new root parameter ( it depends whether the function is searching through the left or right sub tree ).Ultimately the recursive calls will come to a point where the most recent local tree is empty and at that point the new node will be added.*/

void  output (struct node *t, int level)

{

int i;

if (t)

{

output(t->right, level+1);

printf("\n");

for (i = 0; i < level; i++)

printf("   ");

printf("%d,%d (level)", t->info,level);

printf("\n");

 output(t->left, level+1);

}

}

void main()

{

int info,xx=0;

char choice='y';

struct node *t,*root=NULL,*rr;

clrscr();

 while(choice != 'n')

{

t=create ();

/* This function will create a linked list node and the node will be returned.*/

if(xx==0)

 rr=t;

/* pointer rr will store the address of the first node of the tree.*/

xx++;

printf("\n Tree is ");

root=add(t,root);

/* add () function takes two arguments, the current created node address t and the pointer  root to add the current created node in the tree (value small than the root or equal to the root will be inserted at the left branch of the tree root otherwise will be inserted at the right of the root).So after execution of this statement root will point the last inserted node of the tree.*/

output(rr,0);

/* To display the tree output () function is called with the root of the tree as the first argument and zero

  level as the second argument*/

fflush(stdin);

printf("\n Enter choice--'n' to break:");

scanf("%c",&choice);

}

}