NADUI_LAB9

// BFS & DFS Mixed! ------------- NB: Here are lots of spelling mistake,Because this whole bunch of LAB 9 codes collected from Toma!She also collected from someone who did all these shits!//

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

struct node
{
    char name;
    struct edge* edges;
}*A,*B,*C,*D,*E,*F;

struct edge
{
    char name[10];
    edge* next_edge;
    node* dest_node;
}*AB,*AC,*BD,*BE,*CF;

struct Queue
{
    struct node* name;
    Queue *next;
}*head=NULL,*tail=NULL;

//declared queue//
const int size=10;
int queue[size];
int fornt=-1,rear=-1;

//declared functions//
node* creat_node(char n);
edge* createdges(char name[20], node *dNode);
void creat_graph();
void dfs(node* nd);
void bfs(node* nd);
void enqueue(node* n);
node* dequeue();

int main()
{
    creat_graph();
    printf("Depth First Search Is:");
    dfs(A);
    printf("\nBreath first search is:A");
    bfs(A);
    getch();
}
node* creat_node(char n)
{
    struct node *temp=(node*)malloc(sizeof(node));
    temp->name=n;
    temp->edges=NULL;
    return temp;
}
edge* createdges(char name[20], node *dNode)
{
     edge *temp=(edge*)malloc(sizeof(edge));
     strcpy(temp->name,name);
     temp->dest_node=dNode;
     temp->next_edge=NULL;
     return temp;
}
void creat_graph()
{
    //creating Node//
    A=creat_node('A');
    B=creat_node('B');
    C=creat_node('C');
    D=creat_node('D');
    E=creat_node('E');
    F=creat_node('F');
    //craetiing Edge//
    AB=createdges("AB",B);
    AC=createdges("AC",C);
    BD=createdges("BD",D);
    BE=createdges("BE",E);
    CF=createdges("CF",F);
    //creating Link between node and enge//
    A->edges=AB;
    AB->next_edge=AC;
    B->edges=BD;
    BD->next_edge=BE;
    C->edges=CF;
}
void dfs(node* nd)
{

    if(nd!=NULL)
    {
        printf("%c",*nd);
        edge *temp;
        node* ndc;
        temp=nd->edges;
        while (temp!=NULL)
        {
            ndc=temp->dest_node;
            dfs(ndc);
            temp=temp->next_edge;
        }
    }
}
void enqueue(node* n)
{
    Queue *std=(Queue*)malloc(sizeof(Queue));
    std->name=n;
    if (head==NULL)
    {
        std->next=NULL;
        head=std;
    }
    else
    {
        std->next=NULL;
        tail->next=std;
    }
    tail=std;
}
node* dequeue()
{
    node* p;
    if (head!=NULL)
    {
        p=head->name;
        head=head->next;
        return p;
    }
    else
    {
        return NULL;
    }
}
void bfs(node* nd)
{

    if (nd!=NULL)
    {
        edge* temp;
        edge* ch;
        node*ndc;
        temp=nd->edges;
        while (temp!=NULL)
        {
            ndc=temp->dest_node;
            ch=ndc->edges;
            printf("%c",*ndc);
            if (ch!=NULL)
            {
                enqueue(ndc);
            }
            temp=temp->next_edge;
        }
    }
    nd=dequeue();
        if (nd!=NULL)
        {
            bfs(nd);
        }
}

//------------------------------------------------------------END----------------------------------------------------------------------



//--------------------------------------------------S--T--A--R---T--------------------------------------------------------------------


/*BINARY SEARCH TREE*/

#include<stdio.h>


void quicksort(int a[1000], int first, int last)
{
    int marker, i, j, temp;

    if (first<last)
    {
        marker = first;
        i = first;
        j = last;

        while (i<j)
        {
            while (a[i] <= a[marker] && i<last)
                i++;
            while (a[j]>a[marker])
                j--;
            if (i<j)
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        temp = a[j];
        a[j] = a[marker];
        a[marker] = temp;

        quicksort(a, first, j - 1);
        quicksort(a, j + 1, last);
    }
}



int main()
{

    int n = 10, i, a[10] = { 5, 4, 8, 2, 1, 6, 8, 1, 31 };
    quicksort(a, 0, n - 1);
    for (i = 0; i<n; i++)
    {
        printf("%d ", a[i]);
    }

    return 0;
}


----------------------------------------------------END--------------------------------------------------------------------------------


// Inorder, Postorder, Preorder!

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

struct tree
{
    int value;
    tree *left;
    tree *right;
}*head;

void create(int x)
{
    struct  tree *temp,*temp1;
    int flag=0;
    if(head==NULL)
    {
        head=(tree*)malloc(sizeof(tree));
        head->value=x;
        head->left=NULL;
        head->right=NULL;
        return;
    }
    temp=head;
    while(temp!=NULL)
    {
        if(x>temp->value)
        {
            temp1=temp;
            temp=temp->right;
            flag=0;
        }
        else if(x<temp->value)
        {
            temp1=temp;
            temp=temp->left;
            flag=1;
        }
        else
        {
            temp1=temp;
            temp=temp->right;
            flag=0;
        }
    }
    temp=(tree*)malloc(sizeof(tree));
    temp->value=x;
    temp->left=NULL;
    temp->right=NULL;
    if(flag==0)
    {
        temp1->right=temp;
    }
    else
    {
        temp1->left=temp;
    }
}
void in(tree *base)
{
    if(base!=NULL)
    {
        in(base->left);

        printf("%d ",base->value);
        in(base->right);

    }
}
void pre(tree *base)
{
    if(base!=NULL)
    {
        printf("%d ",base->value);
        in(base->left);
        in(base->right);

    }
}
void post(tree *base)
{
    if(base!=NULL)
    {

        in(base->left);
        in(base->right);
        printf("%d ",base->value);

    }
}

void min()
{
    tree *temp;
    temp=head;
    while(temp->left!=NULL)
    {
        temp=temp->left;
    }
    printf("%d is minimum\n",temp->value);


}
void search(int x)
{
    tree *temp;
    temp=head;
    if(x==temp->value)
    {
        printf("found\n");
        return;
    }
    if(x>temp->value)
    {
        while(temp!=NULL)
        {
            if(temp->value==x)
            {
                printf("found\n");
                return;
            }
            temp=temp->right;
        }
        printf("not found\n");
    }
    else
    {
        while(temp!=NULL)
        {
            if(temp->value==x)
            {
                printf("found\n");
                return;
            }
            temp=temp->left;
        }
        printf("not found\n");
    }
}


void main()
{
    int value=0,choice=0;

    while(1)
    {
        printf("\n1->INSERT\n");
        printf("2->INORDER\n");
        printf("3->PREORDER\n");
        printf("4->POSTORDER\n");
        printf("5->MINIMUM\n");


        scanf("%d",&choice);
        switch (choice)
        {
        case 1:
            printf("Enter the value\n");
            scanf("%d", &value);
            create(value);
            printf("Value Inserted\n");
            break;
        case 2:
            in(head);
            break;
        case 3:
            pre(head);
            break;
        case 4:
            post(head);
            break;
        case 5:
            min();
            break;
        case 6:
            printf("Enter the value\n");
            scanf("%d", &value);
            search(value);
            break;
        default:
            break;
        }

    }


}



---------------------------------------END---------------------------------------------------------------------------------------------