bsearchtree.cpp

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

#define FALSE_VALUE 0
#define TRUE_VALUE 1

struct treeNode
{
    int item;
    struct treeNode * left; //points to left child
    struct treeNode * right; //points to right child
};

struct treeNode * root;

void initializeTree()
{
    root = 0;
}

struct treeNode * searchItem(struct treeNode * node, int item)
{
    if(node==0) return 0;
    if(node->item==item) return node; //found, return node
    struct treeNode * t = 0;
    if(item < node->item)
        t = searchItem(node->left, item); //search in the left sub-tree
    else
        t = searchItem(node->right, item); //search in the right sub-tree
    return t;
};


struct treeNode * makeTreeNode(int item)
{
    struct treeNode * node ;
    node = (struct treeNode *)malloc(sizeof(struct treeNode));
    node->item = item;
    node->left = 0;
    node->right = 0;
    return node;
};

struct treeNode * insertItem(struct treeNode * node, int item)
{
    if(node==0) //insert as the root as the tree is empty
    {
        struct treeNode * newNode = makeTreeNode(item);
        root = newNode;
        return newNode;
    }

    if(node->item==item) return 0; //already an item exists, so return NULL

    if(item<node->item && node->left==0) //insert as the left child
    {
        struct treeNode * newNode = makeTreeNode(item);
        node->left = newNode;
        return newNode;
    }

    if(item>node->item && node->right==0) //insert as the right child
    {
        struct treeNode * newNode = makeTreeNode(item);
        node->right = newNode;
        return newNode;
    }

    if(item<node->item)
        return insertItem(node->left, item); //insert at left sub-tree
    else
        return insertItem(node->right, item); //insert at right sub-tree
}



int calcNodeHeight(struct treeNode * node) //return height of a node
{
    if(node==0) return -1;
    int l, r;
    l = calcNodeHeight(node->left);
    r = calcNodeHeight(node->right);
    if(l>r) return l+1;
    else return r+1;
}


int calcHeight(int item) //return height of an item in the tree
{
    struct treeNode * node = 0;
    node = searchItem(root, item);
    if(node==0) return -1; //not found
    else return calcNodeHeight(node);
}

int getSize(struct treeNode * node)
{
    if(node==0)
    {
        return 0;
    }
    else
    {
        return getSize(node->left)+1+getSize(node->right);
    }

}



int calcDepth(int item)//return depth of an item in the tree
{
    struct treeNode * node = 0;
    node = searchItem(root, item);
    if(node==0) return -1; //not found
    else
    {
        int co=0;
        struct treeNode *temp=root;
        while(temp->item!=item)
        {
            co++;
            if(item<temp->item)
            {
                temp=temp->left;
            }
            else
            {
                temp=temp->right;
            }
        }
        return co;
    }

}
int calcNodeDepth(struct treeNode * node) //return depth of a node
{
    if(node==0) return -1;
    else
    {

        return calcDepth(node->item);


    }
}
struct treeNode * getParent(struct treeNode *root,struct treeNode *node)
{
    if(root==0||node==0)
    {
        return 0;
    }
    else if((root->left!=0&&root->left->item==node->item)||(root->right!=0&&root->right->item==node->item))
    {
        return root;
    }
    else
    {
        struct treeNode *f=getParent(root->right,node);
        if(f==0)
        {
            f=getParent(root->left,node);
        }
        return f;
    }
};
int getMinItem() //returns the minimum item in the tree
{
    struct treeNode *temp=root;
    while(temp->left!=0)
    {
        temp=temp->left;
    }
    return temp->item;
}

int getMaxItem() //returns the maximum item in the tree
{
    struct treeNode *temp=root;
    while(temp->right !=0)
    {
        temp=temp->right;
    }
    return temp->item;
}
struct treeNode* MinItem(struct treeNode *node) //returns the minimum item in the tree
{
    struct treeNode *temp=node;
    while(temp->left!=0)
    {
        temp=temp->left;
    }
    return temp;
}
struct treeNode * deleteNode(struct treeNode *node,int item)
{

    if (node == 0) return node;


    if (item  < node->item )
        node->left = deleteNode(node->left, item );


    else if (item  > node->item )
        node->right = deleteNode(node->right, item );


    else
    {

        if (node->left ==0)
        {
            struct treeNode *t = node->right;
            free(node);
            return t;
        }
        else if (node->right == 0)
        {
            struct treeNode *t = node->left;
            free(node);
            return t;
        }


        struct treeNode* t = MinItem(node->right);


        node->item = t->item;


        node->right = deleteNode(node->right, t->item);
    }
    return node;
};



int deleteItem(struct treeNode * node, int item)
{
    struct treeNode *p=searchItem(root,item);
    if(p==0)
    {
        return FALSE_VALUE;
    }
    root=deleteNode(root,item);
    return TRUE_VALUE;


}



int rangeSearch(struct treeNode * node, int leftBound, int rightBound) //returns number of items in the
{

    if(node==0) return 0;
    else
    {
        int countLeft = rangeSearch(node->left, leftBound, rightBound);
        int countRight = rangeSearch(node->right, leftBound, rightBound);
        if(node->item >= leftBound && node->item <= rightBound)
        {

            return 1 + countLeft + countRight;
        }
        else
        {

            return  countLeft + countRight;
        }
    }

}


void printInOrder(struct treeNode * node, int height)
{
    if(node==0) return ;

    //print left sub-tree
    printInOrder(node->left, height-1);

    //print item
    for(int i=0; i<height; i++)printf("   ");
    printf("%03d\n",node->item);

    //print right sub-tree
    printInOrder(node->right, height-1);
}
void eulurtour(struct treeNode *node)
{
    if(node==0) return ;

    printf("%d ",node->item);


    if(node->left!=0)
    {
        eulurtour(node->left);
        printf("%d ",node->item);
    }
    if(node->right!=0)
    {
        eulurtour(node->right);
        printf("%d ",node->item);
    }

}


int main(void)
{
    initializeTree();
    while(1)
    {
        printf("1. Insert item. 2. Delete item. 3. Search item. \n");
        printf("4. Print height of tree. 5. Print height of an item. \n");
        printf("6. PrintInOrder. 7.getSize of the tree 8.Print depth of a node\n");
        printf(" 9.print depth of item 10.print minimum item of the tree \n");
        printf("11. print maximum item  of the tree 12.Search numbers of node in range 13. exit\n");
        int ch;
        scanf("%d",&ch);
        if(ch==1)
        {
            int item;
            scanf("%d", &item);
            insertItem(root, item);
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==2)
        {
            int item;
            scanf("%d", &item);
            deleteItem(root, item);
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==3)
        {
            int item;
            scanf("%d", &item);
            struct treeNode * res = searchItem(root, item);
            if(res!=0) printf("Found.\n");
            else printf("Not found.\n");
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==4)
        {
            int height = calcNodeHeight(root);
            printf("Height of tree = %d\n", height);
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==5)
        {
            int item;
            scanf("%d", &item);
            int height = calcHeight(item);
            printf("Height of %d = %d\n", item, height);
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==6)
        {
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }

        else if(ch==7)
        {
            printf("%d\n",getSize(root));
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==8)
        {
            int item;
            scanf("%d",&item);

            int n=calcNodeDepth(searchItem(root,item));
            printf("%d\n",n);
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==9)
        {
            int item;
            scanf("%d",&item);
            int d=calcDepth(item);
            printf("%d\n",d);
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==10)
        {
            printf("%d\n",getMinItem());
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==11)
        {
            printf("%d\n",getMaxItem());
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==12)
        {
            int lbound,rbound;
            scanf("%d%d",&lbound,&rbound);
            int n=rangeSearch(root,lbound,rbound);
            printf("%d\n",n);
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else
        {
            eulurtour(root);
            printf("\n");
        }
    }

}