Concept of trees in C:

The concept of trees is same to real world tree. In real word every tree has roots, and can have many branches. Each branch can have sub-branches. If you look at branches and sub-branches as a whole, the combination looks like a tree (lets call it a sub-tree). Same is the case of a tree in programming jargon. There is only one difference in plotting the trees. A real world tree has roots on the downside while in C programming, a tree is upside down which has roots on the top and sub-trees below that. Tree is a variation of linked lists.

Here in programming the most commonly used tree is a binary tree. Now lets come to data-structural jargon. A binary tree is a tree in a tree (data structure) in which each node (say current node) has addresses of 2 next possible nodes. The current node is called parent node and these next 2 nodes are called children of that node. We'll call them left child and right child. From the current node, if you want to come down, you have 2 options (either you can come on left child or the right child).

You people have seen that we can traverse a singly linked list in one direction and doubly linked list in two directions in the similar way in a tree you can reach max three nodes from a current node. So in a binary tree each node has only 2 address pointers, you can traverse only in the down direction. If you want to traverse the tree in both the directions (downward as well as upward), each node must be having address of its parent node also.

Here the node structure is a bit different. You can think of a binary tree as a continuation of linked lists from singly to doubly to binary tree. Let me explain further. In node of a singly connected linked list we have one single pointer pointing to next node and in node of a doubly connected linked list we have 2 pointers which can point to other 2 nodes (next and previous nodes). Similarly in a node of a binary tree we have 3 pointers which can point to 3 other nodes one to parent, one to left child, one to right child so that we can traverse easily in both the directions.

program 78: do everything with linked list

The need:
This is a program to show almost all basic operations on linked lists. This program is just a combination of various programs of linked lists written by me. This is written in a way that you can pick data and function definitions and can use as-it-is in other programs.
The code:
------------------------------------------------------------

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

// defining data-type node 
struct linked_list 
{ 
    int num;
    struct linked_list *next;
}; 
typedef struct linked_list node ;   //defining datatype node 

//declaration of functions 

node *create_list(node *p); 
node *reverse(node *p); 
int count (node *p); 
void print(node *p); 
node *insert(node *p); 
node *find(node *p,int a); 
node *hatana(node *p); 
node *insert_sort(node *head,int n); 
void sort(node *p); 
node *rearrange(node *p); 

main() 
{ 
    int i;
    node *head=NULL ;
    printf("This is a program to do with linked list .\n\n");
    lebel:
    printf("Options :\n(1)Create linked list.\n(2)view list.\n(3)Insert element.\n(4)Delete Element.\n");
    printf("(5)To arrange list in increasing order.\n");
    printf("(6)To remove double entries .\n(7)to reverse the list\n(8)Exit program.\n");
    scanf("%d",&i);
    switch(i)
    {
        case 1 :
                printf("Enter element numbers .\n");
                printf("Type -999 to end :\n");
                head=create_list(head);
                printf("List created successfully .\nNumber of items in the list are %d.\n\n\n",count(head));
                goto lebel;
        case 2 :
                print(head);
                goto lebel ;
        case 3 :         
                head=insert(head);
                goto lebel ;
        case 4 :         
                head=hatana(head);
                goto lebel ;
        case 5 :
                sort(head);
                printf("\nsorted in increasing order\n\n");
                goto lebel;
        case 6 :
                rearrange(head);
                printf("\nduplicate entries deleted\n\n");
                goto lebel;
        case 7 :
                head=reverse(head);
                printf("\nList reversed\n\n");
                goto lebel;
        case 8 :
                exit (0);
                break;         
        default:     
                printf("Invalid Choice !!!.\n");
                goto lebel ;
                break;
    }
     
     
    return 0;
        
}                //main ends here 

node *create_list(node *list) 
{ 
    int i;
    list=NULL;
    scanf("%d",&i);
    if(i!=-999)
    {
        list=(node*)malloc(sizeof(node));
        list->num=i;
        list->next=create_list(list->next);
    }
    return list;
} 

node *reverse(node *p) 
{ 
    node *temp=NULL,*rev=NULL;
    while(p)
    {
        temp=p;
        p=p->next;
        temp->next=rev;
        rev=temp;
    }
    return(rev);
} 

int count (node *list) 
{ 
    if(list==NULL)
    return 0;
    else
    return (1+count(list->next));            //recursion 
} 


void print(node *list) 
{ 
    if(list==NULL)
    printf("The list is empty.\n\n");
    else
    {
        printf("%d-->",list->num);
        if(list->next==NULL)
        printf("END\n\n\n");
        else
        print(list->next);            //recursion 
    }
} 



node *find(node *list, int key)            //This function returns the node after which 
{     
    if(list->next)
    {                                    //the key is found .                             
        if(list->next->num == key)     /* key found */ 
            return(list);
        else if(list->next->next == NULL)    /* end */ 
            return(NULL);
        else
        find(list->next, key);
    }
    else
    return NULL;
} 



node *insert(node *head) 
{ 
    node *new_node;          /* pointer to new node */ 
    node *n1=head;        /* pointer to node preceding key node */ 
    int key;
    int x;            /* new item (number) to be inserted */ 
    if(!head)
    {
        printf("\nlist is not created yet.\n\n");
        return head;
    }
    printf("What value you want to insert?");
    scanf("%d", &x);
    printf("before which key item ? (type -999 if to be inserted last) ");
    scanf("%d", &key);

    if(key==-999)        /* insert new node at last*/ 
    {
        while(n1->next)
            n1=n1->next;    //navigate to last node 
            
        new_node = (node *)malloc(sizeof(node));
        new_node->num = x;
        new_node->next = n1->next;
        n1->next = new_node;
    }
    else if(head->num == key)        /* new node is first */ 
    {
        new_node = (node *)malloc(sizeof(node));
        new_node->num = x;
        new_node->next = head;
        head = new_node;
    }
    else        /* find key node and insert new node */ 
    {            /* before the key node */ 
        n1 = find(head, key);    /* find key node */

        if(n1 == NULL&&key!=-999)
           printf("\n key is not found !!!\n\n");
            
        else        /* insert new node */ 
        {
          new_node = (node *)malloc(sizeof(node));
          new_node->num = x;
          new_node->next = n1->next;
          n1->next = new_node;
        }
      }
      return head;
} 



node *hatana(node *list) 
{ 
    void delete_node(node *);
    node *n1,*n2;
    int key;
    if(!list)
    {
        printf("\nlist is not created yet.\n\n");
        return list;
    }
    printf("What value do you want to delete ?");
    scanf("%d",&key);
    if(key==list->num)                        //key is the first node 
    {
        n2=list->next;
        free(list);
        list=n2;
        printf("\n%d is deleted successfully .\n\n",key);
    }
    else
    {
         n1=find (list ,key);
         if(n1)
        {
            delete_node(n1);                        //This function deletes n1->next 
            printf("\n%d is deleted successfully .\n\n",key);
        }
         else
         printf("\nItem is not in the list !!! \n\n\n");
    }
return(list); 
} 


void delete_node(node *list)  //This function deletes list->next 
{ 
    node *n2;
    n2=list->next->next;
    free(list->next);
    list->next=n2;
} 



node *rearrange(node *list) 
{ 
    node *p1;
    sort(list);
    for(p1=list;p1->next!=NULL;p1=p1->next)
    {
        if(p1->num==p1->next->num)
        delete_node(p1);
    }
    return(list);
} 


void sort(node *list) 
{ 
    void exchange(int *s1,int *s2);
    node *p,*q;
    for(p=list;(p->next)!=NULL;p=p->next)
        for(q=list;(q->next)!=NULL;q=q->next)
        {
            if(q->num > q->next->num)            //simple bubble sort 
            exchange(&(q->num),&(q->next->num));
        }
} 

void exchange(int *s1,int *s2) 
{ 
    int temp;
    temp =*s1;
    *s1=*s2;
    *s2=temp;
}

------------------------------------------------------------

Remarks:

This program has a small bug try and find out.