Algorithms

Data Structures

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.

Overview

Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by an address—a bit string that can be itself stored in memory and manipulated by the program. Thus the record and array data structures are based on computing the addresses of data items with arithmetic operations; while the linked data structures are based on storing addresses of data items within the structure itself. Many data structures use both principles,

Fig 1: This is an array data structure in computer programming.

Binary Search Tree

randerson112358

This is a video on inserting elements into a binary search tree.

Download PDF

List of Data Structures different types of data structures

Fig 2: This is a Binary Search Tree data structure in computer programming.

Linked List C Program

Computer Science (compsci112358)

A linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence.

Github: linkedlist.c

Please Subscribe !

►Support this channel for FREE by doing your Amazon shopping through this link (bookmark it!): https://www.amazon.com/?tag=everythingc06-20

Download PDF

Binary Search Tree Worst Case

randerson112358

What is the worst-case time complexity to search an element in a binary search tree ?

Download PDF

Code: Binary Search Tree


/* This is a Binary Search Tree Program Written in the C Programming Language */

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

typedef struct BST
{
    int data;
    struct BST *lchild,*rchild;
}node;

void insert(node *,node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
node *search(node *,int,node **);

void main()
{
 int choice;
 char ans='N';
 int key;
 node *new_node,*root,*tmp,*parent;
 node *get_node();
 root=NULL;
 

 printf("\nProgram For Binary Search Tree ");
 do
 {
   printf("\n1.Create");
   printf("\n2.Search");
   printf("\n3.Recursive Traversals");
   printf("\n4.Exit");
   printf("\nEnter your choice :");
   scanf("%d",&choice);
   
    

   switch(choice)
   {
    case 1:
           do
             {
             new_node=get_node();

             printf("\nEnter The Element ");
             scanf("%d",&new_node->data);

             if(root==NULL)   /* Tree is not Created */
                 root=new_node;
             else
                 insert(root,new_node);

             printf("\nWant To enter More Elements?(y/n)");
             ans=getch();

             }while(ans=='y');

             break;

     case 2:
             printf("\nEnter Element to be searched :");
             scanf("%d",&key);

             tmp = search(root,key,&parent);

			 if(tmp == NULL)
			 	printf("The Tree Is Empty \n");
			 else
             	printf("\nParent of node %d is %d", tmp->data,parent->data);
             
             break;

    case 3:

            if(root==NULL)
                printf("Tree Is Not Created \n");
            else
               {
               printf("\nThe Inorder display : ");
               inorder(root);
               printf("\nThe Preorder display : ");
               preorder(root);
               printf("\nThe Postorder display : ");
               postorder(root);
               }

            break;
    }
 }while(choice!=4);
}
/*
  Get new Node 
*/
node *get_node()
 {
 node *temp;
 temp=(node *)malloc(sizeof(node));
 temp->lchild=NULL;
 temp->rchild=NULL;
 return temp;
 }
/*
  This function is for creating a binary search tree 
*/
void insert(node *root,node *new_node)
{
  if(new_node->data < root->data)
     {
     if(root->lchild==NULL)
         root->lchild = new_node;
     else
         insert(root->lchild,new_node);
     }

  if(new_node->data > root->data)
     {
     if(root->rchild==NULL)
         root->rchild=new_node;
     else
         insert(root->rchild,new_node);
     }
}
/*
This function is for searching the node from
      binary Search Tree
*/
node *search(node *root,int key,node **parent)
{
 node *temp;
 temp=root;
    while(temp!=NULL)
    {
      if(temp->data==key)
         {
         printf("\n The %d Element is Present",temp->data);
         return temp;
         }
      *parent=temp;

      if(temp->data>key)
         temp=temp->lchild;
      else
         temp=temp->rchild;
    }
 return NULL;
}
/*
This function displays the tree in inorder fashion
*/
void inorder(node *temp)
{
   if(temp!=NULL)
    {
    inorder(temp->lchild);
    printf("%d ",temp->data);
    inorder(temp->rchild);
    }
}
/*
This function displays the tree in preorder fashion
*/
void preorder(node *temp)
{
 if(temp!=NULL)
    {
    printf("%d ",temp->data);
    preorder(temp->lchild);
    preorder(temp->rchild);
    }
}

/*
This function displays the tree in postorder fashion
*/
void postorder(node *temp)
{
 if(temp!=NULL)
    {
    postorder(temp->lchild);
    postorder(temp->rchild);
    printf("%d ",temp->data);
    }
}