Prim's Algorithm in C

     /*  Program to implement Prim's algorithm  */  
      
    #include<stdio.h>  
    #include<stdlib.h>  
    struct node  
    {  
        int key;  
        int data;  
        struct node *par;  
    };  
    struct node *n[20];  
    struct edge  
    {  
        int wt;  
        struct node *src,*des;  
    };  
    struct edge *e[20][20];  
    void makeset(int i)  
    {  
         n[i]=(struct node *)malloc(sizeof(struct node));  
         n[i]->data=i;  
         n[i]->key=9999;  
         n[i]->par=NULL;  
    }  
    int main()  
    {  
        int tn,i,adm[20][20],q[20],s,j,w,temp,k;  
        printf("Enter the total no. of nodes ");  
        scanf("%d",&tn);  
        for(i=0;i<=tn;i++)  
        {  
            for(j=0;j<=tn;j++)  
            {  
                adm[i][j]=0;  
            }  
        }  
        printf("\nEnter the weights for the following edges ::\n");  
        for(i=1;i<=tn;i++)  
        {  
            makeset(i);  
            q[i]=i;  
            for(j=i+1;j<=tn;j++)  
            {  
                printf("%d  %d: ",i,j);  
                scanf("%d",&w);  
                if(w==0)  
                w=9999;  
                e[i][j]=(struct edge *)malloc(sizeof(struct edge));  
                e[i][j]->wt=w;           
                e[i][j]->src=n[i];      
                e[i][j]->des=n[j];      
                adm[i][j]=1;  
                adm[j][i]=1;  
            }  
        }  
        j=1;  
        while(j<=tn)  
        {  
            q[j]=0;  
            temp=j;  
            for(k=1;k<=tn;k++)  
            {  
                if(adm[temp][k]==1 && q[k]==k)  
                {  
                    if(e[temp][k]->wt<n[k]->key)  
                    {  
                        n[k]->par=n[temp];    
                        n[k]->key=e[temp][k]->wt;  
                    }  
                }  
            }  
        j++;  
        }  
        for(j=2;j<=tn;j++)  
        {  
            k=(n[j]->par)->data;  
            printf("output is %d : %d - %d\n",k,j,e[k][j]->wt);  
        }  
    } 

Read More...

Kruskal's Algorithm in C

        /* Program to implement Kruskal's Algorithm */
      
    #include<stdio.h>  
    #include<stdlib.h>       
    void makeset();  
    void graph(int);  
    void kruskal();  
    struct node *findset(struct node *);  
    void union1(struct node *,struct node *);  
      
    int j=0;  
    struct node //Declare the structure of a node  
    {  
        int data,rank;  
        struct node *next,*parent;  
    };       
    struct edge //Declare the structure of a edge  
    {  
        int len;  
        struct node *src,*destination;  
    };        
    struct node *head[10];  
    struct edge *e[40];       
    int main()  
    {  
        int n,i;  
        printf("\nEnter no.of vertices in the graph : ");  
        scanf("%d",&n);  
        for(i=1;i<=n;i++)  
        {  
            makeset(i); //initialise each vertex  
        }  
        graph(n);  
        kruskal();      
    }      
    void makeset(int a)  
    {  
        struct node *x;  
        x=(struct node*)malloc(sizeof(struct node));  
        x->data=a;  
        x->parent=x;  
        x->rank=0;  
        x->next=NULL;  
        head[a]=x;  
    }     
    void graph(int n)   //here input neighbours of each vertex & the weight of edges  
    {  
        int i,k,l,len;  
        int dest;  
        for(i=1;i<=n;i++)  
        {  
            printf("\nfor vertex %d Enter no. of edges ",i);  
            scanf("%d",&l);  
            for(k=1;k<=l;k++)  
            {  
            printf("Enter destination vertex for %dth edge for vertex %d ",k,i);  
            scanf("%d",&dest);  
            j++;  
            e[j]=(struct edge*)malloc(sizeof(struct edge));  
            e[j]->src=head[i];  
            e[j]->destination=head[dest];  
            printf("Enter length of edge : ");  
            scanf("%d",&len);  
            e[j]->len=len;  
            }  
        }  
    }      
    void kruskal()  //Apply actual concept of kruskal  
    {  
        int i,k,l,p;  
        struct edge *temp;  
        i=1;  
        while(i<j)   //sort the edges with increasing order of their weights  
        {       //using insertion sort  
            p=i;  
            k=i+1;  
            while(k<=j)  
            {  
                if(e[p]->len>e[k]->len)  
                {  
                    p=k;  
                }  
                k++;  
            }  
            if(p!=i)  
            {  
            temp=e[p];  
            e[p]=e[i];  
            e[i]=temp;  
            }  
            i++;  
        }  
        printf("\nMST includes the following edges that are :\n");  
        for(i=1;i<=j;i++)  
        {  
            if(findset(e[i]->src)!=findset(e[i]->destination))    //if representative  
            {                           //of src & dest. are different  
            union1((findset(e[i]->src)),(findset(e[i]->destination)));    //then make connection  
            printf("\n%d->%d",e[i]->src->data,e[i]->destination->data);  //b/w them  
            }  
        }  
    }       
    struct node *findset(struct node *a)    //return the represenative of node  
    {  
        if(a!=a->parent)  
        {  
            a->parent=findset(a->parent);  
        }  
        return a->parent;  
    }      
    void union1(struct node *x,struct node *y)  //join the two vertex if desired  
    {  
        if(x->rank>y->rank)  
            y->parent=x;  
        else  
            x->parent=y;  
        if(x->rank==y->rank)  
        y->rank=y->rank+1;  
    }  

Read More...

Binary Search Tree in Java

    /* Program to implement search function, count nodes function and three traversal functions of a binary tree using recursion */

      import java.io.*;
    class TreeNode
    {
        TreeNode left,right;
        int data;
        public TreeNode()
        {
            data=0;
            left=right=null;
        }
        public TreeNode(int n)
        {
            data=n;
            left=right=null;
        }
        public void disp()
        {
            System.out.println(data + " ");
        }
        public TreeNode getleft()
        {
            return left;
        }
        public TreeNode getright()
        {
            return right;
        }
        public void setdata(int d)
        {
            data=d;
        }
        public int getdata()
        {
            return data;
        }
    }
   
    class BinaryTree
    {
        TreeNode root;
        public BinaryTree()
        {
            root=null;
        }
        public int countnodes()
        {
            return countnodes(root);
        }
        private int countnodes(TreeNode r)
        {
            if(r==null)
                return 0;
            else
            {
                int l=1;
                l=l+countnodes(r.getleft());
                l=l+countnodes(r.getright());
                return l;
            }
        }
        public boolean search(int value)
        {
            return search(root,value);
        }
        private boolean search(TreeNode r,int val)
        {
            boolean found=false;
            while((r!=null) && !found)
            {
                int rval=r.getdata();
                if(val < rval)
                    r=r.getleft();
                else if(val > rval)
                    r=r.getright();
                else
                {
                    found=true;
                    break;
                }
                found=search(r,val);
            }
            return found;
        }
        public void inoder()
        {
            inorder(root);
        }
        private void inorder(TreeNode r)
        {
            if(r!=null)
            {
                inorder(r.getleft());
                System.out.print(r.getdata() + "  ");
                inorder(r.getright());
            }
        }
        public void preoder()
        {
            preorder(root);
        }
        private void preorder(TreeNode r)
        {
            if(r!=null)
            {
                System.out.print(r.getdata() + "  ");
                preorder(r.getleft());               
                preorder(r.getright());
            }
        }
        public void postoder()
        {
            postorder(root);
        }
        private void postorder(TreeNode r)
        {
            if(r!=null)
            {
                postorder(r.getleft());               
                postorder(r.getright());
                System.out.print(r.getdata() + "  ");
            }
        }
    }

    class bttest
    {
        protected static BinaryTree bt;       
        public static void main(String args[])
        {
            int val;
            bt=new BinaryTree();
            System.out.println("\nPost order traversal of the tree is :  ");
            bt.postorder(); 
            System.out.println("\nPre order traversal of the tree is :  ");
            bt.preorder(); 
            System.out.println("\nInorder order traversal of the tree is :  ");
            bt.inorder();
            int l=bt.countnodes();
            System.out.println("\nNo. of nodes : " +l);
            try
            {
                System.out.println("\nEnter search item : ");
                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
                val=Integer.parseInt(br.readLine());
                if(bt.search(val))
                    System.out.println("Item exists in the tree");
                else
                    System.out.println("Item does not exist in the tree");
            }
            catch(Exception e)
            {
                System.out.println(e);
            }
            System.out.println("\n");
        }
    } 

Read More...

Minimum Cost of a Spanning Tree in C Programming

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
 
struct lledge
{
    int v1, v2 ;
    float cost ;
    struct lledge *next ;
} ;
 
int stree[5] ;
int count[5] ;
int mincost ;
 
struct lledge * kminstree ( struct lledge *, int ) ;
int getrval ( int ) ;
void combine ( int, int ) ;
void del ( struct lledge * ) ;
 
void main( )
{
    struct lledge *temp, *root ;
    int i ;
 
    clrscr( ) ;
 
    root = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;
 
    root -> v1 = 4 ;
    root -> v2 = 3 ;
    root -> cost = 1 ;
    temp = root -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;
 
    temp -> v1 = 4 ;
    temp -> v2 = 2 ;
    temp -> cost = 2 ;
    temp -> next =(struct lledge*)malloc(sizeof(struct lledge)) ;
 
    temp = temp -> next ;
    temp -> v1 = 3 ;
    temp -> v2 = 2 ;
    temp -> cost = 3 ;
    temp -> next =(struct lledge*)malloc(sizeof(struct lledge));
 
    temp = temp -> next ;
    temp -> v1 = 4 ;
    temp -> v2 = 1 ;
    temp -> cost = 4 ;
    temp -> next = NULL ;
 
    root = kminstree ( root, 5 ) ;
 
    for ( i = 1 ; i <= 4 ; i++ )
        printf ( "\nstree[%d] -> %d", i, stree[i] ) ;
    printf ( "\nThe minimum cost of spanning tree is %d", mincost ) ;
    del ( root ) ;
 
    getch( ) ;
}
struct lledge * kminstree ( struct lledge *root, int n )
{
    struct lledge *temp = NULL ;
    struct lledge *p, *q ;
    int noofedges = 0 ;
    int i, p1, p2 ;
 
    for ( i = 0 ; i < n ; i++ )
        stree[i] = i ;
    for ( i = 0 ; i < n ; i++ )
        count[i] = 0 ;
 
    while ( ( noofedges < ( n - 1 ) ) && ( root != NULL ) )
    {
        p = root ;
 
        root = root -> next ;
 
        p1 = getrval ( p -> v1 ) ;
        p2 = getrval ( p -> v2 ) ;
 
        if ( p1 != p2 )
        {
            combine ( p -> v1, p -> v2 ) ;
            noofedges++ ;
            mincost += p -> cost ;
            if ( temp == NULL )
            {
                temp = p ;
                q = temp ;
            }
            else
            {
                q -> next = p ;
                q = q -> next ;
            }
            q -> next = NULL ;
        }
    }
    return temp ;
}
 
int getrval ( int i )
{
    int j, k, temp ;
    k = i ;
    while ( stree[k] != k )
        k = stree[k] ;
    j = i ;
    while ( j != k )
    {
        temp = stree[j] ;
        stree[j] = k ;
        j = temp ;
    }
    return k ;
}
 
void combine ( int i, int j )
{
    if ( count[i] < count[j] )
        stree[i] = j ;
    else
    {
        stree[j] = i ;
        if ( count[i] == count[j] )
            count[j]++ ;
    }
}
 
void del ( struct lledge *root )
{
    struct lledge *temp ;
 
    while ( root != NULL )
    {
        temp = root -> next ;
        free ( root ) ;
        root = temp ;
    }
}

Read More...

Deleting a node from a Binary Tree in C Programming

/* Deleting in Binary Tree */
/* DELET_BT.C */

# include<stdio.h>
# include<malloc.h>

struct NODE
{
    int Info;
    struct NODE *Left_Child;
    struct NODE *Right_Child;
};

int depth;
void Output (struct NODE *, int );
struct NODE *Delet_Node (struct NODE *, int );
struct NODE *Create_Tree (int , struct NODE *);
struct NODE * DELE(struct NODE *, struct NODE *);

/* Output function */

void Output(struct NODE *T, int Level)
{
    int i;
    if (T)
    {
        Output(T->Right_Child, Level+1);
        printf("\n");
        for (i = 0; i < Level; i++)
            printf("  ");
        printf("%c", T->Info);
        Output(T->Left_Child, Level+1);
    }
}

/* Delete a node in the binary tree */

struct NODE * DELE(struct NODE *Node1, struct NODE *Node)
{
    struct NODE *DNode;
    if (Node1->Right_Child != NULL)
        Node1->Right_Child = DELE(Node1->Right_Child, Node);
    else
    {
        DNode = Node1;
        Node->Info = Node1->Info;
        Node1 = Node1->Left_Child;
        free(DNode);
    }
    return (Node1);
}

/* Deletion in binary tree */

struct NODE * Delet_Node (struct NODE *Node, int Info)
{
    struct NODE *Temp;

    if (Node == NULL)
    {
        printf("\n Information does not exist in the above tree");
        return (Node);
    }
    else
    {
        if (Info < Node->Info )
            Node->Left_Child = Delet_Node (Node->Left_Child, Info);
        else
            if (Info > Node->Info )

                Node->Left_Child = Delet_Node (Node->Right_Child, Info);
            else
            {
                Temp = Node;
                if (Temp->Right_Child == NULL)
                {
                    Node = Temp->Left_Child;
                    free(Temp);
                }
                else
                    if (Temp->Left_Child == NULL)
                    {
                        Node = Temp->Right_Child;
                        free(Temp);
                    }
                    else
                        Temp->Left_Child = DELE(Temp->Left_Child, Temp);
            }
    }
    return(Node);
}

/* Create binary tree */

struct NODE *  Create_Tree (int Info, struct NODE *Node)
{
    if (Node == NULL)
    {
        Node = (struct NODE *) malloc(sizeof(struct NODE));
        Node->Info = Info;
        Node->Left_Child = NULL;
        Node->Right_Child = NULL;
        return (Node);
    }

    /* Test for the left child */

    if (Info < Node->Info)

        Node->Left_Child = Create_Tree (Info, Node->Left_Child);

    else

        /* Test for the right child */

        if (Info >= Node->Info)

            Node->Right_Child = Create_Tree (Info, Node->Right_Child);
    return(Node);
}

/* Function main */

void main()
{
    int Number = 0;
    int Info ;
    char choice;
    int depth;
    struct NODE *T = (struct NODE *) malloc(sizeof(struct NODE));
    T = NULL;
    printf("\n Input choice 'b' to break:");
    choice = getchar();

    while(choice != 'b')
    {
        fflush(stdin);
        printf("\n Input information of the node: ");
        scanf("%c", &Info);
        T = Create_Tree(Info, T);
        Number++;
        fflush(stdin);
        printf("\n Input choice 'b' to break:");
        choice = getchar();
    }
    fflush(stdin);
    printf("\n Number of elements in the list is %d", Number);
    printf("\n Tree is \n");
    Output(T, 1);

    printf("\n Input the information to which want remove from the above tree: ");
    scanf("%c", &Info);

    T = Delet_Node(T, Info);
    printf("\n Tree after deletion of a node: ");
    Output(T, 1);
} 

Read More...

How to create a Tree in C Programming ?

/* Create TREE */

# include<stdio.h>
# include<malloc.h>
struct NODE
{
    int Info;
    struct NODE *Left_Child;
    struct NODE *Right_Child;
};
struct NODE *Create_Tree (int , struct NODE *);
void Output(struct NODE *, int );

/* Function to create a tree */

struct NODE * Create_Tree (int Info, struct NODE *Node)
{
    if (Node == NULL)
    {
        Node = (struct NODE *) malloc( sizeof(struct NODE ));
        Node->Info = Info;
        Node->Left_Child = NULL;
        Node->Right_Child = NULL;
        return (Node);
    }

    /* Test for the left child */
    if (Node->Info >= Info )
        Node->Left_Child = Create_Tree (Info, Node->Left_Child);
    else

        /* Set all the rest of the elements as right child */

        Node->Right_Child = Create_Tree (Info, Node->Right_Child);
    return(Node);
}

/* Output function */

void  Output(struct NODE *T, int Level)
{
    int i;
    if (T)
    {
        Output(T->Right_Child, Level+1);
        printf("\n ");
        for (i = 0; i < Level; i++)
            printf("   ");
        printf("%d", T->Info);
        printf("\n");
        Output(T->Left_Child, Level+1);
    }
}

/* Function main */

void main()
{
    int Info ;
    char choice;
    struct NODE *T = (struct NODE *) malloc(sizeof(struct NODE *));
    T = NULL;
    printf("\n Input choice 'b' to break:");
    choice = getchar();
    while(choice != 'b')
    {
        printf("\n Input information of the node: ");
        scanf("%d", &Info);
        T = Create_Tree (Info, T);
        printf("\n Tree is ");
        Output(T, 1);
        printf("\n Input choice 'b' to break:");
        choice = getchar();
    }
}

Read More...

Create a Red-Black Tree in C programming

/* red-black tree */

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


/* implementation dependend declarations */
typedef enum {
    STATUS_OK,
    STATUS_MEM_EXHAUSTED,
    STATUS_DUPLICATE_KEY,
    STATUS_KEY_NOT_FOUND
} statusEnum;

typedef int keyType;            /* type of key */

/* user data stored in tree */
typedef struct {
    int stuff;                  /* optional related data */
} recType;

#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/* implementation independent declarations */
/* Red-Black tree description */
typedef enum { BLACK, RED } nodeColor;

typedef struct nodeTag {
    struct nodeTag *left;       /* left child */
    struct nodeTag *right;      /* right child */
    struct nodeTag *parent;     /* parent */
    nodeColor color;            /* node color (BLACK, RED) */
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
} nodeType;

#define NIL &sentinel           /* all leafs are sentinels */
nodeType sentinel = { NIL, NIL, 0, BLACK, 0};

nodeType *root = NIL;               /* root of Red-Black tree */

void rotateLeft(nodeType *x) {

   /**************************
    *  rotate node x to left *
    **************************/

    nodeType *y = x->right;

    /* establish x->right link */
    x->right = y->left;
    if (y->left != NIL) y->left->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
        root = y;
    }

    /* link x and y */
    y->left = x;
    if (x != NIL) x->parent = y;
}

void rotateRight(nodeType *x) {

   /****************************
    *  rotate node x to right  *
    ****************************/

    nodeType *y = x->left;

    /* establish x->left link */
    x->left = y->right;
    if (y->right != NIL) y->right->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
        root = y;
    }

    /* link x and y */
    y->right = x;
    if (x != NIL) x->parent = y;
}

void insertFixup(nodeType *x) {

   /*************************************
    *  maintain Red-Black tree balance  *
    *  after inserting node x           *
    *************************************/

    /* check Red-Black properties */
    while (x != root && x->parent->color == RED) {
        /* we have a violation */
        if (x->parent == x->parent->parent->left) {
            nodeType *y = x->parent->parent->right;
            if (y->color == RED) {

                /* uncle is RED */
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                /* uncle is BLACK */
                if (x == x->parent->right) {
                    /* make x a left child */
                    x = x->parent;
                    rotateLeft(x);
                }

                /* recolor and rotate */
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(x->parent->parent);
            }
        } else {

            /* mirror image of above code */
            nodeType *y = x->parent->parent->left;
            if (y->color == RED) {

                /* uncle is RED */
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                /* uncle is BLACK */
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

statusEnum insert(keyType key, recType *rec) {
    nodeType *current, *parent, *x;

   /***********************************************
    *  allocate node for data and insert in tree  *
    ***********************************************/

    /* find future parent */
    current = root;
    parent = 0;
    while (current != NIL) {
        if (compEQ(key, current->key)) 
            return STATUS_DUPLICATE_KEY;
        parent = current;
        current = compLT(key, current->key) ?
            current->left : current->right;
    }

    /* setup new node */
    if ((x = malloc (sizeof(*x))) == 0)
        return STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = NIL;
    x->right = NIL;
    x->color = RED;
    x->key = key;
    x->rec = *rec;

    /* insert node in tree */
    if(parent) {
        if(compLT(key, parent->key))
            parent->left = x;
        else
            parent->right = x;
    } else {
        root = x;
    }

    insertFixup(x);

    return STATUS_OK;
}

void deleteFixup(nodeType *x) {

   /*************************************
    *  maintain Red-Black tree balance  *
    *  after deleting node x            *
    *************************************/

    while (x != root && x->color == BLACK) {
        if (x == x->parent->left) {
            nodeType *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft (x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight (w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft (x->parent);
                x = root;
            }
        } else {
            nodeType *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight (x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft (w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight (x->parent);
                x = root;
            }
        }
    }
    x->color = BLACK;
}

statusEnum delete(keyType key) {
    nodeType *x, *y, *z;

   /*****************************
    *  delete node z from tree  *
    *****************************/

    /* find node in tree */
    z = root;
    while(z != NIL) {
        if(compEQ(key, z->key)) 
            break;
        else
            z = compLT(key, z->key) ? z->left : z->right;
    }
    if (z == NIL) return STATUS_KEY_NOT_FOUND;

    if (z->left == NIL || z->right == NIL) {
        /* y has a NIL node as a child */
        y = z;
    } else {
        /* find tree successor with a NIL node as a child */
        y = z->right;
        while (y->left != NIL) y = y->left;
    }

    /* x is y's only child */
    if (y->left != NIL)
        x = y->left;
    else
        x = y->right;

    /* remove y from the parent chain */
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root = x;

    if (y != z) {
        z->key = y->key;
        z->rec = y->rec;
    }


    if (y->color == BLACK)
        deleteFixup (x);

    free (y);
    return STATUS_OK;
}

statusEnum find(keyType key, recType *rec) {

   /*******************************
    *  find node containing data  *
    *******************************/

    nodeType *current = root;
    while(current != NIL) {
        if(compEQ(key, current->key)) {
            *rec = current->rec;
            return STATUS_OK;
        } else {
            current = compLT (key, current->key) ?
                current->left : current->right;
        }
    }
    return STATUS_KEY_NOT_FOUND;
}


void main(int argc, char **argv) {
    int maxnum, ct, n;
    recType rec;
    keyType key;
    statusEnum status;
    maxnum = atoi(argv[1]);
    printf("maxnum = %d\n", maxnum);
    for (ct = maxnum; ct; ct--) {
        key = rand() % 9 + 1;
        if ((status = find(key, &rec)) == STATUS_OK) {
            status = delete(key);
            if (status) printf("fail: status = %d\n", status);
        } else {
            status = insert(key, &rec);
            if (status) printf("fail: status = %d\n", status);
        }
    }
}

Read More...

How to find depth of a Binary Tree in C Programming ?

# include<stdio.h> 
# include<malloc.h> 
typedef struct NODE 
{ 
    char Info; 
    struct NODE *Left_Child; 
    struct NODE *Right_Child; 
}ND; 
int depth = 0; 
void Output ( ND*, int ); 
int Depth (ND *, int ); 
ND *Create_Tree (char , ND *); 
void Output(ND *T, int Level) 
{ 
    int i; 
    if (T) 
    { 
        Output(T->Right_Child, Level+1); 
        printf("\n"); 
        for (i = 0; i < Level; i++) 
            printf("  "); 
        printf("%c", T->Info); 
        Output(T->Left_Child, Level+1); 
    } 
} 
int Depth (ND *Node, int Level) 
{ 
    if (Node != NULL) 
    { 
        if (Level > depth) 
            depth = Level; 
        Depth (Node->Left_Child, Level + 1); 
        Depth (Node->Right_Child, Level + 1); 
    } 
    return (depth); 
} 
ND *  Create_Tree (char Info, ND *Node) 
{ 
    if (Node == NULL) 
    { 
        Node = (ND *) malloc(sizeof(ND)); 
        Node->Info = Info; 
        Node->Left_Child = NULL; 
        Node->Right_Child = NULL; 
        return (Node); 
    } 
    if (Info < Node->Info) 
        Node->Left_Child = Create_Tree (Info, Node->Left_Child); 
    else 
        if (Info > Node->Info) 
            Node->Right_Child = Create_Tree (Info, Node->Right_Child); 
    return(Node); 
} 
void main() 
{ 
    int Number = 0; 
    char Info ; 
    char choice; 
    int depth; 
    ND *T = (ND *) malloc(sizeof(ND)); 
    T = NULL; 
    printf("\n Input choice 'b' to break:"); 
    choice = getchar(); 
    while(choice != 'b') 
    { 
        fflush(stdin); 
        printf("\n Input information of the node: "); 
        scanf("%c", &Info); 
        T = Create_Tree(Info, T); 
        Number++; 
        fflush(stdin); 
        printf("\n Input choice 'b' to break:"); 
        choice = getchar(); 
    } 
    printf("\n Number of elements in the list is  %d", Number); 
    printf("\n Tree is \n"); 
    Output(T, 1); 
    depth = Depth(T, 0); 
    printf("\n Depth of the above tree is:  %d", depth); 
} 

Read More...

Threaded Binary Tree in C Programming

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
enum boolean
{
    false = 0,
    true = 1
};
struct thtree
{
    enum boolean isleft ;
    struct thtree *left ;
    int data ;
    struct thtree *right ;
    enum boolen isright ;
} ;
void insert ( struct thtree **, int ) ;
void delete ( struct thtree **, int ) ;
void search ( struct thtree **, int, struct thtree **,struct thtree **, int * ) ;
void inorder ( struct thtree * ) ;
void deltree ( struct thtree ** ) ;
main( )
{
    struct thtree *th_head ;
    th_head = NULL ;  /* empty tree */
    insert ( &th_head, 25 ) ;
    insert ( &th_head, 94 ) ;
    insert ( &th_head, 15 ) ;
    insert ( &th_head, 85) ;
    insert ( &th_head, 102 ) ;
    insert ( &th_head, 125 ) ;
    insert ( &th_head, 176 ) ;
    insert ( &th_head, 159 ) ;
    insert ( &th_head, 767 ) ;
    printf ( "Threaded binary tree before deletion:\n" ) ;
    inorder ( th_head ) ;
    delete ( &th_head, 10 ) ;
    printf ( "\nThreaded binary tree after deletion:\n" ) ;
    inorder ( th_head ) ;
    delete ( &th_head, 14 ) ;
    printf ( "\nThreaded binary tree after deletion:\n" ) ;
    inorder ( th_head ) ;
    delete ( &th_head, 8 ) ;
    printf ( "\nThreaded binary tree after deletion:\n" ) ;
    inorder ( th_head ) ;
    delete ( &th_head, 13 ) ;
    printf ( "\nThreaded binary tree after deletion:\n" ) ;
    inorder ( th_head ) ;
    deltree ( &th_head ) ;
}
void insert ( struct thtree **s, int num )
{
    struct thtree *p, *z, *head = *s ;
    z = malloc ( sizeof ( struct thtree ) ) ;
    z -> isleft = true ;  /* indicates a thread */
    z -> data = num ;  /* assign new data */
    z -> isright = true ;  /* indicates a thread */
    if ( *s == NULL )
    {
        head = malloc ( sizeof ( struct thtree ) ) ;
        head -> isleft = false ;
        head -> left = z ;  
        head -> data = -9999 ;  
        head -> right = head ;  
        head -> isright = false ;
        *s = head ;
        z -> left = head ;  
        z -> right = head ;  
    }
    else
    {
        p = head -> left ;
      while ( p != head )
        {
            if ( p -> data > num )
            {
                if ( p -> isleft != true )  
                    p = p -> left ;
                else
                {
                    z -> left = p -> left ;
                    p -> left = z ;
                    p -> isleft = false ;  
                    z -> isright = true ;
                    z -> right = p ;
                    return ;
                }
            }
            else
            {
                if ( p -> data < num )
                {
                    if ( p -> isright != true )
                        p = p -> right ;
                    else
                    {
                        z -> right = p -> right ;
                        p -> right = z ;
                        p -> isright = false ;  
                        z -> isleft = true ;
                        z -> left = p ;
                        return ;
                    }
                }
            }
        }
    }
}

void delete ( struct thtree **root, int num )
{
    int found ;
    struct thtree *parent, *x, *xsucc ;
    if ( *root == NULL )
    {
        printf ( "\nTree is empty" ) ;
        return ;
    }
    parent = x = NULL ;
    search ( root, num, &parent, &x, &found ) ;

if ( found == false )
    {
        printf ( "\nData to be deleted, not found" ) ;
        return ;
    }    
if ( x -> isleft == false && x -> isright == false )
    {
        parent = x ;
        xsucc = x -> right ;

        while ( xsucc -> isleft == false )
        {
            parent = xsucc ;
            xsucc = xsucc -> left ;
        }
        x -> data = xsucc -> data ;
        x = xsucc ;
    }   
if ( x -> isleft == true && x -> isright == true )
    {        
if ( parent == NULL )
        {
            ( *root ) -> left = *root ;
            ( *root ) -> isleft = true ;

            free ( x ) ;
            return ;
        }
        if ( parent -> right == x )
        {
            parent -> isright = true ;
            parent -> right = x -> right ;
        }
        else
        {
            parent -> isleft = true ;
            parent -> left = x -> left ;
        }

        free ( x ) ;
        return ;
    }
if ( x -> isleft == true && x -> isright == false )
    {        
if ( parent == NULL )
        {
            ( *root ) -> left = x -> right ;
            free ( x ) ;
            return ;
        }
        if ( parent -> left == x )
        {
            parent -> left = x -> right ;
            x -> right -> left = x -> left ;
        }
        else
        {
            parent -> right = x -> right ;
            x -> right -> left = parent ;
        }

        free ( x ) ;
        return ;
    }   
if ( x -> isleft == false && x -> isright == true )
    {        
if ( parent == NULL )
        {
            parent = x ;
            xsucc = x -> left ;

            while ( xsucc -> right == false )
            xsucc = xsucc -> right ;

            xsucc -> right = *root ;

            ( *root ) -> left = x -> left ;

            free ( x ) ;
            return ;
        }
        if ( parent -> left == x )
        {
            parent -> left = x -> left ;
            x -> left -> right = parent ;
        }
        else
        {
            parent -> right = x -> left ;
            x -> left -> right = x -> right ;
        }

        free ( x ) ;
        return ;
    }
}
void search ( struct thtree **root, int num, struct thtree **par,  struct thtree **x, int *found )
{
    struct thtree *q ;
    q = ( *root ) -> left ;
    *found = false ;
    *par = NULL ;
    while ( q != *root )
    {       
if ( q -> data == num )
        {
            *found = true ;
            *x = q ;
            return ;
        }
        *par = q ;
        if ( q -> data > num )
        {
            if ( q -> isleft == true )
            {
                *found = false ;
                x = NULL ;
                return ;
            }
            q = q -> left ;
        }
        else
        {
            if ( q -> isright == true )
            {
                *found = false ;
                *x = NULL ;
                return ;
            }
            q = q -> right ;
        }
    }
}
void inorder ( struct thtree *root )
{
    struct thtree *p ;
    p = root -> left ;
    while ( p != root )
    {
        while ( p -> isleft == false )
            p = p -> left ;
        printf ( "%d\t", p -> data ) ;
        while ( p -> isright == true )
        {
            p = p -> right ;
            if ( p == root )
                break ;
            printf ( "%d\t", p -> data ) ;
        }
        p = p -> right ;
    }
}
void deltree ( struct thtree **root )
{
    while ( ( *root ) -> left != *root )
        delete ( root, ( *root ) -> left -> data ) ;
}

Read More...

B-Tree Programming in C

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
typedef long eAdrType;          
typedef long bAdrType;          
#define CC_EQ           0
#define CC_GT           1
#define CC_LT          -1
typedef int (*bCompType)(const void *key1, const void *key2);
int maxHeight;          
int nNodesIns;          
int nNodesDel;          
int nKeysIns;           
int nKeysDel;           
int nDiskReads;         
int nDiskWrites;        
int bErrLineNo;
typedef enum {false, true} bool;
typedef enum {
    bErrOk,
    bErrKeyNotFound,
    bErrDupKeys,
    bErrSectorSize,
    bErrFileNotOpen,
    bErrFileExists,
    bErrIO,
    bErrMemory 
} bErrType;
typedef void *bHandleType;

typedef struct {                
    char *iName;                
    int keySize;                
    bool dupKeys;               
    int sectorSize;             
    bCompType comp;             
} bOpenType;
bErrType bOpen(bOpenType info, bHandleType *handle);
bErrType bClose(bHandleType handle);
bErrType bInsertKey(bHandleType handle, void *key, eAdrType rec);
bErrType bDeleteKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindFirstKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindLastKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindNextKey(bHandleType handle, void *key, eAdrType *rec);
bErrType bFindPrevKey(bHandleType handle, void *key, eAdrType *rec);
#define bAdr(p) *(bAdrType *)(p)
#define eAdr(p) *(eAdrType *)(p)
#define childLT(k) bAdr((char *)k - sizeof(bAdrType))
#define key(k) (k)
#define rec(k) eAdr((char *)(k) + h->keySize)
#define childGE(k) bAdr((char *)(k) + h->keySize + sizeof(eAdrType))
#define leaf(b) b->p->leaf
#define ct(b) b->p->ct
#define next(b) b->p->next
#define prev(b) b->p->prev
#define fkey(b) &b->p->fkey
#define lkey(b) (fkey(b) + ks((ct(b) - 1)))
#define p(b) (char *)(b->p)
#define ks(ct) ((ct) * h->ks)
typedef char keyType;           
typedef struct {
    unsigned int leaf:1;        
    unsigned int ct:15;         
    bAdrType prev;              
    bAdrType next;             
    bAdrType childLT;           
    keyType fkey;              
} nodeType;
typedef struct bufTypeTag {     
    struct bufTypeTag *next;    
    struct bufTypeTag *prev;    
    bAdrType adr;               
    nodeType *p;                
    bool valid;                 
    bool modified;              
} bufType;
typedef struct hNodeTag {
    struct hNodeTag *prev;      
    struct hNodeTag *next;      
    FILE *fp;                   
    int keySize;                
    bool dupKeys;               
    int sectorSize;             
    bCompType comp;             
    bufType root;              
    bufType bufList;            
    void *malloc1;              
    void *malloc2;              
    bufType gbuf;               
    bufType *curBuf;            
    keyType *curKey;            
    unsigned int maxCt;         
    int ks;                     
    bAdrType nextFreeAdr;       
} hNode;
static hNode hList;             
static hNode *h;                
#define error(rc) lineError(__LINE__, rc)
static bErrType lineError(int lineno, bErrType rc) {
    if (rc == bErrIO || rc == bErrMemory)
        if (!bErrLineNo) 
            bErrLineNo = lineno;
    return rc;
}
static bAdrType allocAdr(void) {
    bAdrType adr;
    adr = h->nextFreeAdr;
    h->nextFreeAdr += h->sectorSize;
    return adr;
}
static bErrType flush(bufType *buf) {
    int len;            
    len = h->sectorSize;
    if (buf->adr == 0) len *= 3;        
    if (fseek(h->fp, buf->adr, SEEK_SET)) return error(bErrIO);
    if (fwrite(buf->p, len, 1, h->fp) != 1) return error(bErrIO);
    buf->modified = false;
    nDiskWrites++;
    return bErrOk;
}
static bErrType flushAll(void) {
    bErrType rc;                
    bufType *buf;               
    if (h->root.modified)
        if ((rc = flush(&h->root)) != 0) return rc;
    buf = h->bufList.next;
    while (buf != &h->bufList) {
        if (buf->modified)
            if ((rc = flush(buf)) != 0) return rc;
        buf = buf->next;
    }
}
static bErrType assignBuf(bAdrType adr, bufType **b) {
    bufType *buf;               
    bErrType rc;                

    if (adr == 0) {
        *b = &h->root;
        return bErrOk;
    }
    buf = h->bufList.next;
    while (buf->next != &h->bufList) {
        if (buf->valid && buf->adr == adr) break;
        buf = buf->next;
    }
    if (buf->valid) {
        if (buf->adr != adr) {
            if (buf->modified) {
                if ((rc = flush(buf)) != 0) return rc;
            }
            buf->adr = adr;
            buf->valid = false;
        }
    } else {
        buf->adr = adr;
    }
    buf->next->prev = buf->prev;
    buf->prev->next = buf->next;
    buf->next = h->bufList.next;
    buf->prev = &h->bufList;
    buf->next->prev = buf;
    buf->prev->next = buf;
    *b = buf;
    return bErrOk;
}
static bErrType writeDisk(bufType *buf) {
   
    buf->valid = true;
    buf->modified = true;
    return bErrOk;
}
static bErrType readDisk(bAdrType adr, bufType **b) {
    int len;
    bufType *buf;               
    bErrType rc;                
    if ((rc = assignBuf(adr, &buf)) != 0) return rc;
    if (!buf->valid) {
        len = h->sectorSize;
        if (adr == 0) len *= 3;         
        if (fseek(h->fp, adr, SEEK_SET)) return error(bErrIO);
        if (fread(buf->p, len, 1, h->fp) != 1) return error(bErrIO);
        buf->modified = false;
        buf->valid = true;
        nDiskReads++;
    }
    *b = buf;
    return bErrOk;
}
typedef enum { MODE_FIRST, MODE_MATCH } modeEnum;
static int search(
    bufType *buf,
    void *key, 
    eAdrType rec, 
    keyType **mkey,
    modeEnum mode) {
    int cc;                     
    int m;                      
    int lb;                     
    int ub;                     
    bool foundDup;              
    foundDup = false;
    lb = 0; 
    ub = ct(buf) - 1;
    while (lb <= ub) {
        m = (lb + ub) / 2;
        *mkey = fkey(buf) + ks(m);
        cc = h->comp(key, key(*mkey));
        if (cc < 0)
            ub = m - 1;
        else if (cc > 0)
            lb = m + 1;
        else {
             if (h->dupKeys) {
                switch (mode) {
                case MODE_FIRST:
                    ub = m - 1;
                    foundDup = true;
                    break;
                case MODE_MATCH:
                    if (rec < rec(*mkey)) {
                        ub = m - 1;
                        cc = CC_LT;
                    } else if (rec > rec(*mkey)) {
                        lb = m + 1;
                        cc = CC_GT;
                    } else {
                        return CC_EQ;
                    }
                    break;
                }
            } else {
                return cc;
            }
        }
    }
    if (ct(buf) == 0) {
        *mkey = fkey(buf);
        return CC_LT;
    }
    if (h->dupKeys && (mode == MODE_FIRST) && foundDup) {
        
        *mkey += ks(1);
        return CC_EQ;
    }
    return cc;
}
static bErrType scatterRoot(void) {
    bufType *gbuf;
    bufType *root;
    root = &h->root;
    gbuf = &h->gbuf;
    memcpy(fkey(root), fkey(gbuf), ks(ct(gbuf)));
    childLT(fkey(root)) = childLT(fkey(gbuf));
    ct(root) = ct(gbuf);
    leaf(root) = leaf(gbuf);
    return bErrOk;
}
static bErrType scatter(bufType *pbuf, keyType *pkey, int is, bufType **tmp) {
    bufType *gbuf;              
    keyType *gkey;              
    bErrType rc;                
    int iu;                     
    int k0Min;                  
    int knMin;                 
    int k0Max;                  
    int knMax;                  
    int sw;                     
    int len;                    
    int base;                  
    int extra;                  
    int ct;
    int i;
    gbuf = &h->gbuf;
    gkey = fkey(gbuf);
    ct = ct(gbuf);
    iu = is;
    if (leaf(gbuf)) {
        k0Max= h->maxCt - 1;
        knMax= h->maxCt - 1;
        k0Min= (h->maxCt / 2) + 1;
        knMin= (h->maxCt / 2) + 1;
    } else {
        k0Max = h->maxCt - 1;
        knMax = h->maxCt;
        k0Min = (h->maxCt / 2) + 1;
        knMin = ((h->maxCt+1) / 2) + 1;
    }
    while(1) {
        if (iu == 0 || ct > (k0Max + (iu-1)*knMax)) {
            if ((rc = assignBuf(allocAdr(), &tmp[iu])) != 0) 
                return rc;
            if (leaf(gbuf)) {
                 if (iu == 0) {
                    prev(tmp[0]) = 0;
                    next(tmp[0]) = 0;
                } else {
                    prev(tmp[iu]) = tmp[iu-1]->adr;
                    next(tmp[iu]) = next(tmp[iu-1]);
                    next(tmp[iu-1]) = tmp[iu]->adr;
                }
            }
            iu++;
            nNodesIns++;
        } else if (iu > 1 && ct < (k0Min + (iu-1)*knMin)) {
            iu--;
            if (leaf(gbuf) && tmp[iu-1]->adr) {
                next(tmp[iu-1]) = next(tmp[iu]);
            }
            next(tmp[iu-1]) = next(tmp[iu]);
            nNodesDel++;
        } else {
            break;
        }
    }
    base = ct / iu;
    extra = ct % iu;
    for (i = 0; i < iu; i++) {
        int n;
        n = base;
        if (i && extra) {
            n++;
            extra--;
        }
        ct(tmp[i]) = n;
    }
    if (iu != is) {
        if (leaf(gbuf) && next(tmp[iu-1])) {
            bufType *buf;
            if ((rc = readDisk(next(tmp[iu-1]), &buf)) != 0) return rc;
            prev(buf) = tmp[iu-1]->adr;
            if ((rc = writeDisk(buf)) != 0) return rc;
        }
        sw = ks(iu - is);
        if (sw < 0) {
            len = ks(ct(pbuf)) - (pkey - fkey(pbuf)) + sw;
            memmove(pkey, pkey - sw, len);
        } else {
            len = ks(ct(pbuf)) - (pkey - fkey(pbuf));
            memmove(pkey + sw, pkey, len);
        }
        if (ct(pbuf))
            ct(pbuf) += iu - is;
        else
            ct(pbuf) += iu - is - 1;
    }
    for (i = 0; i < iu; i++) {
        if (leaf(gbuf)) {
             childLT(fkey(tmp[i])) = 0;
            if (i == 0) {
                childLT(pkey) = tmp[i]->adr;
            } else {
                memcpy(pkey, gkey, ks(1));
                childGE(pkey) = tmp[i]->adr;
                pkey += ks(1);
            }
        } else {
            if (i == 0) {
                
                childLT(fkey(tmp[i])) = childLT(gkey);
                
                childLT(pkey) = tmp[i]->adr;
            } else {
               childLT(fkey(tmp[i])) = childGE(gkey);
                memcpy(pkey, gkey, ks(1));
                childGE(pkey) = tmp[i]->adr;
                gkey += ks(1);
                pkey += ks(1);
                ct(tmp[i])--;
            }
        }
        memcpy(fkey(tmp[i]), gkey, ks(ct(tmp[i])));
        leaf(tmp[i]) = leaf(gbuf);
        gkey += ks(ct(tmp[i]));
    }
    leaf(pbuf) = false;
    if ((rc = writeDisk(pbuf)) != 0) return rc;
    for (i = 0; i < iu; i++)
        if ((rc = writeDisk(tmp[i])) != 0) return rc;
    return bErrOk;
}
static bErrType gatherRoot(void) {
    bufType *gbuf;
    bufType *root;
    root = &h->root;
    gbuf = &h->gbuf;
    memcpy(p(gbuf), root->p, 3 * h->sectorSize);
    leaf(gbuf) = leaf(root);
    ct(root) = 0;
    return bErrOk;
}
static bErrType gather(bufType *pbuf, keyType **pkey, bufType **tmp) {
    bErrType rc;                
    bufType *gbuf;
    keyType *gkey;
    if (*pkey == lkey(pbuf))
        *pkey -= ks(1);
    if ((rc = readDisk(childLT(*pkey), &tmp[0])) != 0) return rc;
    if ((rc = readDisk(childGE(*pkey), &tmp[1])) != 0) return rc;
    if ((rc = readDisk(childGE(*pkey + ks(1)), &tmp[2])) != 0) return rc;
    gbuf = &h->gbuf;
    gkey = fkey(gbuf);
    childLT(gkey) = childLT(fkey(tmp[0]));
    memcpy(gkey, fkey(tmp[0]), ks(ct(tmp[0])));
    gkey += ks(ct(tmp[0]));
    ct(gbuf) = ct(tmp[0]);
    if (!leaf(tmp[1])) {
        memcpy(gkey, *pkey, ks(1));
        childGE(gkey) = childLT(fkey(tmp[1]));
        ct(gbuf)++;
        gkey += ks(1);
    }
    memcpy(gkey, fkey(tmp[1]), ks(ct(tmp[1])));
    gkey += ks(ct(tmp[1]));
    ct(gbuf) += ct(tmp[1]);
    if (!leaf(tmp[2])) {
        memcpy(gkey, *pkey+ks(1), ks(1));
        childGE(gkey) = childLT(fkey(tmp[2]));
        ct(gbuf)++;
        gkey += ks(1);
    }
    memcpy(gkey, fkey(tmp[2]), ks(ct(tmp[2])));
    ct(gbuf) += ct(tmp[2]);
    leaf(gbuf) = leaf(tmp[0]);
    return bErrOk;
}
bErrType bOpen(bOpenType info, bHandleType *handle) {
    bErrType rc;               
    int bufCt;                  
    bufType *buf;               
    int maxCt;                  
    bufType *root;
    int i;
    nodeType *p;
    if ((info.sectorSize < sizeof(hNode)) || (info.sectorSize % 4))
        return bErrSectorSize;

    maxCt = info.sectorSize - (sizeof(nodeType) - sizeof(keyType));
    maxCt /= sizeof(bAdrType) + info.keySize + sizeof(eAdrType);
    if (maxCt < 6) return bErrSectorSize;
    if ((h = malloc(sizeof(hNode))) == NULL) return error(bErrMemory);
    memset(h, 0, sizeof(hNode));
    h->keySize = info.keySize;
    h->dupKeys = info.dupKeys;
    h->sectorSize = info.sectorSize;
    h->comp = info.comp;
    h->ks = sizeof(bAdrType) + h->keySize + sizeof(eAdrType);
    h->maxCt = maxCt;
    bufCt = 7;
    if ((h->malloc1 = malloc(bufCt * sizeof(bufType))) == NULL) 
        return error(bErrMemory);
    buf = h->malloc1;
    if ((h->malloc2 = malloc((bufCt+6) * h->sectorSize + 2 * h->ks)) == NULL) 
        return error(bErrMemory);
    p = h->malloc2;
    h->bufList.next = buf;
    h->bufList.prev = buf + (bufCt - 1);
    for (i = 0; i < bufCt; i++) {
        buf->next = buf + 1;
        buf->prev = buf - 1;
        buf->modified = false;
        buf->valid = false;
        buf->p = p;
        p = (nodeType *)((char *)p + h->sectorSize);
        buf++;
    }
    h->bufList.next->prev = &h->bufList;
    h->bufList.prev->next = &h->bufList;
    root = &h->root;
    root->p = p;
    p = (nodeType *)((char *)p + 3*h->sectorSize);
    h->gbuf.p = p;      
    h->curBuf = NULL;
    h->curKey = NULL;
    if ((h->fp = fopen(info.iName, "r+b")) != NULL) {
        if ((rc = readDisk(0, &root)) != 0) return rc;
        if (fseek(h->fp, 0, SEEK_END)) return error(bErrIO);
        if ((h->nextFreeAdr = ftell(h->fp)) == -1) return error(bErrIO);
    } else if ((h->fp = fopen(info.iName, "w+b")) != NULL) {
      
        memset(root->p, 0, 3*h->sectorSize);
        leaf(root) = 1;
        h->nextFreeAdr = 3 * h->sectorSize;
    } else {
        /* something's wrong */
        free(h);
        return bErrFileNotOpen;
    }
    if (hList.next) {
        h->prev = hList.next;
        h->next = &hList;
        h->prev->next = h;
        h->next->prev = h;
    } else {
        /* first item in hList */
        h->prev = h->next = &hList;
        hList.next = hList.prev = h;
    }

    *handle = h;
    return bErrOk;
}
bErrType bClose(bHandleType handle) {
    h = handle;
    if (h == NULL) return bErrOk;
    if (h->next) {
        h->next->prev = h->prev;
        h->prev->next = h->next;
    }
    if (h->fp) {
        flushAll();
        fclose(h->fp);
    }
    if (h->malloc2) free(h->malloc2);
    if (h->malloc1) free(h->malloc1);
    free(h);
    return bErrOk;
}
bErrType bFindKey(bHandleType handle, void *key, eAdrType *rec) {
    keyType *mkey;              
    bufType *buf;               
    bErrType rc;                
    h = handle;
    buf = &h->root;
    while (1) {
        if (leaf(buf)) {
            if (search(buf, key, 0, &mkey, MODE_FIRST) == 0) {
                *rec = rec(mkey);
                h->curBuf = buf; h->curKey = mkey;
                return bErrOk;
            } else {
                return bErrKeyNotFound;
            }
        } else {
            if (search(buf, key, 0, &mkey, MODE_FIRST) < 0) {
                if ((rc = readDisk(childLT(mkey), &buf)) != 0) return rc;
            } else {
                if ((rc = readDisk(childGE(mkey), &buf)) != 0) return rc;
            }
        }
    }
}
bErrType bInsertKey(bHandleType handle, void *key, eAdrType rec) {
    int rc;                     
    keyType *mkey;              
    int len;                    
    int cc;                     
    bufType *buf, *root;
    bufType *tmp[4];
    unsigned int keyOff;
    bool lastGEvalid;           
    bool lastLTvalid;           
    bAdrType lastGE;            
    unsigned int lastGEkey;     
    int height;                 
    h = handle;
    root = &h->root;
    lastGEvalid = false;
    lastLTvalid = false;
    if (ct(root) == 3 * h->maxCt) {
        if ((rc = gatherRoot()) != 0) return rc;
        if ((rc = scatter(root, fkey(root), 0, tmp)) != 0) return rc;
    }
    buf = root;
    height = 0;
    while(1) {
        if (leaf(buf)) {
        if (height > maxHeight) maxHeight = height;
            switch(search(buf, key, rec, &mkey, MODE_MATCH)) {
            case CC_LT:  
                if (!h->dupKeys && h->comp(key, mkey) == CC_EQ)
                    return bErrDupKeys;
                break;
            case CC_EQ:  
                return bErrDupKeys;
                break;
            case CC_GT:  
                if (!h->dupKeys && h->comp(key, mkey) == CC_EQ)
                    return bErrDupKeys;
                mkey += ks(1);
                break;
            }
            keyOff = mkey - fkey(buf);
            len = ks(ct(buf)) - keyOff;
            if (len) memmove(mkey + ks(1), mkey, len);
            memcpy(key(mkey), key, h->keySize);
            rec(mkey) = rec;
            childGE(mkey) = 0;
            ct(buf)++;
            if ((rc = writeDisk(buf)) != 0) return rc;
            if (!keyOff && lastLTvalid) {
                bufType *tbuf;
                keyType *tkey;
                if ((rc = readDisk(lastGE, &tbuf)) != 0) return rc;
                tkey = fkey(tbuf) + lastGEkey;
                memcpy(key(tkey), key, h->keySize);
                rec(tkey) = rec;
                if ((rc = writeDisk(tbuf)) != 0) return rc;
            }
            nKeysIns++;
            break;
        } else {
           bufType *cbuf;      
           height++;
           if ((cc = search(buf, key, rec, &mkey, MODE_MATCH)) < 0) {
                if ((rc = readDisk(childLT(mkey), &cbuf)) != 0) return rc;
            } else {
                if ((rc = readDisk(childGE(mkey), &cbuf)) != 0) return rc;
            }
            if (ct(cbuf) == h->maxCt) {
                if ((rc = gather(buf, &mkey, tmp)) != 0) return rc;
                if ((rc = scatter(buf, mkey, 3, tmp)) != 0) return rc;
                if ((cc = search(buf, key, rec, &mkey, MODE_MATCH)) < 0) {
                    if ((rc = readDisk(childLT(mkey), &cbuf)) != 0) return rc;
                } else {
                    if ((rc = readDisk(childGE(mkey), &cbuf)) != 0) return rc;
                }
            }
            if (cc >= 0 || mkey != fkey(buf)) {
                lastGEvalid = true;
                lastLTvalid = false;
                lastGE = buf->adr;
                lastGEkey = mkey - fkey(buf);
                if (cc < 0) lastGEkey -= ks(1);
            } else {
                if (lastGEvalid) lastLTvalid = true;
            }
            buf = cbuf;
        }
    }

    return bErrOk;
}
bErrType bDeleteKey(bHandleType handle, void *key, eAdrType *rec) {
    int rc;                     
    keyType *mkey;              
    int len;                    
    int cc;                     
    bufType *buf;               
    bufType *tmp[4];
    unsigned int keyOff;
    bool lastGEvalid;           
    bool lastLTvalid;           
    bAdrType lastGE;            
    unsigned int lastGEkey;     
    bufType *root;
    bufType *gbuf;
    h = handle;
    root = &h->root;
    gbuf = &h->gbuf;
    lastGEvalid = false;
    lastLTvalid = false;
    buf = root;
    while(1) {
        if (leaf(buf)) {
           if (search(buf, key, *rec, &mkey, MODE_MATCH) == 0)
                *rec = rec(mkey);
            else
                return bErrKeyNotFound;
            keyOff = mkey - fkey(buf);
            len = ks(ct(buf)-1) - keyOff;
            if (len) memmove(mkey, mkey + ks(1), len);
            ct(buf)--;
            if ((rc = writeDisk(buf)) != 0) return rc;
            if (!keyOff && lastLTvalid) {
                bufType *tbuf;
                keyType *tkey;
                if ((rc = readDisk(lastGE, &tbuf)) != 0) return rc;
                tkey = fkey(tbuf) + lastGEkey;
                memcpy(key(tkey), mkey, h->keySize);
                rec(tkey) = rec(mkey);
                if ((rc = writeDisk(tbuf)) != 0) return rc;
            }
            nKeysDel++;
            break;
        } else {
            bufType *cbuf;      
            if ((cc = search(buf, key, *rec, &mkey, MODE_MATCH)) < 0) {
                if ((rc = readDisk(childLT(mkey), &cbuf)) != 0) return rc;
            } else {
                if ((rc = readDisk(childGE(mkey), &cbuf)) != 0) return rc;
            }
            if (ct(cbuf) == h->maxCt/2) {
               if ((rc = gather(buf, &mkey, tmp)) != 0) return rc;
                if (buf == root
                && ct(root) == 2 
                && ct(gbuf) < (3*(3*h->maxCt))/4) {
                    scatterRoot();
                    nNodesDel += 3;
                    continue;
                }
                if ((rc = scatter(buf, mkey, 3, tmp)) != 0) return rc;
                if ((cc = search(buf, key, *rec, &mkey, MODE_MATCH)) < 0) {
                    if ((rc = readDisk(childLT(mkey), &cbuf)) != 0) return rc;
                } else {
                    if ((rc = readDisk(childGE(mkey), &cbuf)) != 0) return rc;
                }
            }
            if (cc >= 0 || mkey != fkey(buf)) {
                lastGEvalid = true;
                lastLTvalid = false;
                lastGE = buf->adr;
                lastGEkey = mkey - fkey(buf);
                if (cc < 0) lastGEkey -= ks(1);
            } else {
                if (lastGEvalid) lastLTvalid = true;
            }
            buf = cbuf;
        }
    }

    return bErrOk;
}
bErrType bFindFirstKey(bHandleType handle, void *key, eAdrType *rec) {
    bErrType rc;                
    bufType *buf;              
    h = handle;
    buf = &h->root;
    while (!leaf(buf)) {
        if ((rc = readDisk(childLT(fkey(buf)), &buf)) != 0) return rc;
    }
    if (ct(buf) == 0) return bErrKeyNotFound;
    memcpy(key, key(fkey(buf)), h->keySize);
    *rec = rec(fkey(buf));
    h->curBuf = buf; h->curKey = fkey(buf);
    return bErrOk;
}
bErrType bFindLastKey(bHandleType handle, void *key, eAdrType *rec) {
    bErrType rc;                
    bufType *buf;               
    h = handle;
    buf = &h->root;
    while (!leaf(buf)) {
        if ((rc = readDisk(childGE(lkey(buf)), &buf)) != 0) return rc;
    }
    if (ct(buf) == 0) return bErrKeyNotFound;
    memcpy(key, key(lkey(buf)), h->keySize);
    *rec = rec(lkey(buf));
    h->curBuf = buf; h->curKey = lkey(buf);
    return bErrOk;
}
bErrType bFindNextKey(bHandleType handle, void *key, eAdrType *rec) {
    bErrType rc;                
    keyType *nkey;              
    bufType *buf;               
    h = handle;
    if ((buf = h->curBuf) == NULL) return bErrKeyNotFound;
    if (h->curKey == lkey(buf)) {
        
        if (next(buf)) {
            
            if ((rc = readDisk(next(buf), &buf)) != 0) return rc;
            nkey = fkey(buf);
        } else {
            
            return bErrKeyNotFound;
        }
    } else {
        
        nkey = h->curKey + ks(1);
    }
    memcpy(key, key(nkey), h->keySize);
    *rec = rec(nkey);
    h->curBuf = buf; h->curKey = nkey;
    return bErrOk;
}
bErrType bFindPrevKey(bHandleType handle, void *key, eAdrType *rec) {
    bErrType rc;               
    keyType *pkey;              
    keyType *fkey;              
    bufType *buf;               
    h = handle;
    if ((buf = h->curBuf) == NULL) return bErrKeyNotFound;
    fkey = fkey(buf);
    if (h->curKey == fkey) {
        
        if (prev(buf)) {
            
            if ((rc = readDisk(prev(buf), &buf)) != 0) return rc;
            pkey = fkey(buf) + ks((ct(buf) - 1));
        } else {
           
            return bErrKeyNotFound;
        }
    } else {
        
        pkey = h->curKey - ks(1);
    }
    memcpy(key, key(pkey), h->keySize);
    *rec = rec(pkey);
    h->curBuf = buf; h->curKey = pkey;
    return bErrOk;
}
int comp(const void *key1, const void *key2) {
    unsigned int const *p1;
    unsigned int const *p2;
    p1 = key1; p2 = key2;
    return (*p1 == *p2) ? CC_EQ : (*p1 > *p2 ) ? CC_GT : CC_LT;
}
int main(void) {
    bOpenType info;
    bHandleType handle;
    bErrType rc;
    unsigned int key;
    remove("t1.dat");
    info.iName = "t1.dat";
    info.keySize = sizeof(int);
    info.dupKeys = false;
    info.sectorSize = 256;
    info.comp = comp;
    if ((rc = bOpen(info, &handle)) != bErrOk) {
        printf("line %d: rc = %d\n", __LINE__, rc);
        exit(0);
    }
    key = 0x11;
    if ((rc = bInsertKey(handle, &key, 0x300)) != bErrOk) {
        printf("line %d: rc = %d\n", __LINE__, rc);
        exit(0);
    }
    bClose(handle);
    printf("statistics:\n");
    printf("    maximum height: %4d\n", maxHeight);
    printf("    nodes inserted: %4d\n", nNodesIns);
    printf("    nodes deleted:  %4d\n", nNodesDel);
    printf("    keys inserted:  %4d\n", nKeysIns);
    printf("    keys deleted:   %4d\n", nKeysDel);
    printf("    disk reads:     %4d\n", nDiskReads);
    printf("    disk writes:    %4d\n", nDiskWrites);
    return 0;
}

Read More...