Thursday, November 26, 2009

Program 2 find the balancing factor of a node in an AVL tree

/*
 *Program to calculate the balancing factor of an AVL Tree
 */

/**
 *Assumptions to run this program:
 *no data of a node is set to 0
 */
#include
#include

#include
#define array_max 100
//function declaration
int left(int);//return the location of left child
int right(int);//returns the location of right child
int traverse(int,int); //traverses to the specific location and returns the position
void postOrder(int);//
int calculateHeight(int);
int compareHeight(int,int);//generates the height of a tree
//stores the tree in an array
int tree[100];
//stores the inorder of an array
int temp_array[100] = {0};

//declare left function
int left(int node)
{
    return 2*node+1;
}
int right(int node)
{
    return 2*node+2;
}

//initilizes all elements to zero
tree[100]={0};

//traverse to d element and return the index of element in that array
int traverse(int item,int n)
{
    if(tree[n] == item)
        return n;
    else if(tree[n] < item)
    {
        n=left(n);
        traverse(item,n);
        return n;
    }
    else
    {
        n=right(n);
        traverse(item,n);
        return n;
    }
}
//compares the height of a tree
int compareHeight(int position,int start)
{
    int l,r;
    l=2*start+1;
    r=2*start+2;
    if(position == l)
        return start+1;
    else if(position == r)
        return start+1;
    else
    {
        compareHeight(position, l);
        compareHeight(position, r);
    }
}

//calculate the post order traversal of the tree and return the index of last element
void postOrder(int pos)//pos stores the index of root node
{
    int i;
    i=0;
    if(tree[pos != 0])
    {
        temp_array[i]=pos;
        postOrder(left(pos));
        postOrder(right(pos));
    }
}

int calculateHeight(int element)
{
    int i,pos;
    i=0;
    while(temp_array[i] != 0)
    {
        i++;
    }
    i--;
    pos = compareHeight(temp_array[i],0);
    return pos;
}

//main function goes here.................
int main()
{
    int i,temp;
    i=0;
    int position;
    int height1,height2;
    int balancingFactor;
    printf("Caution: This program assumes that none of the element in a tree is
#define array_max 1000\n");
    printf("Caution: The tree which you are entering must be a AVL Tree\n");
    printf("Enter the elements of the array\n");
    printf("Enter 0 to exit\n");
    printf("Dont Enter any element as 0\n");
    do
    {
        scanf("%d",&temp);
        if(temp != 0)
        {
            tree[i]=temp;
        }
    }while(temp != 0);
    printf("Enter the element to find the balancing factor\n");
    scanf("%d",&temp);
    position=traverse(temp,0);
    height1=calculateHeight(left(position));
    height2=calculateHeight(right(position));
    balancingFactor=height1-height2;
    printf("The balancing factor of that element is %d",balancingFactor);
    return 0;
}


u may modify this program & implement using linked list

No comments:

Post a Comment