please help e to complete the program

This is a discussion on please help e to complete the program within the C Programming forums, part of the General Programming Boards category; Program to maintain an AVL tree. Code: #include <stdio.h> #include <conio.h> #include <alloc.h> #define FALSE 0 #define TRUE 1 struct ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    2

    Lightbulb please help e to complete the program

    Program to maintain an AVL tree.

    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <alloc.h>
     
    #define FALSE 0
    #define TRUE 1
     
    struct AVLNode
    {
        int data ;
        int balfact ;
        struct AVLNode *left ;
        struct AVLNode *right ;
    } ;
     
    struct AVLNode * buildtree ( struct AVLNode *, int, int * ) ;
    struct AVLNode * deldata ( struct AVLNode *, int, int * ) ;
    struct AVLNode * del ( struct AVLNode *, struct AVLNode *, int * ) ;
    struct AVLNode * balright ( struct AVLNode *, int * ) ;
    struct AVLNode * balleft ( struct AVLNode *, int * ) ;
    void display ( struct AVLNode * ) ;
    void deltree ( struct AVLNode * ) ;
     
    void main( )
    {
        struct AVLNode *avl = NULL ;
        int h ;
     
        clrscr( ) ;
     
        avl = buildtree ( avl, 20, &h ) ;
        avl = buildtree ( avl, 6, &h ) ;
        avl = buildtree ( avl, 29, &h ) ;
        avl = buildtree ( avl, 5, &h ) ;
        avl = buildtree ( avl, 12, &h ) ;
        avl = buildtree ( avl, 25, &h ) ;
        avl = buildtree ( avl, 32, &h ) ;
        avl = buildtree ( avl, 10, &h ) ;
        avl = buildtree ( avl, 15, &h ) ;
        avl = buildtree ( avl, 27, &h ) ;
        avl = buildtree ( avl, 13, &h ) ;
     
        printf ( "\nAVL tree:\n" ) ;
        display ( avl ) ;
     
        avl = deldata ( avl, 20, &h ) ;
        avl = deldata ( avl, 12, &h ) ;
     
        printf ( "\nAVL tree after deletion of a node:\n" ) ;
        display ( avl ) ;
     
        deltree ( avl ) ;
     
        getch( ) ;
    }
     
    /* inserts an element into tree */
    struct AVLNode * buildtree ( struct AVLNode *root, int data, int *h )
    {
        struct AVLNode *node1, *node2 ;
     
        if ( !root )
        {
            root = ( struct AVLNode * ) malloc ( sizeof ( struct AVLNode ) ) ;
            root -> data = data ;
            root -> left = NULL ;
            root -> right = NULL ;
            root -> balfact = 0 ;
            *h = TRUE ;
            return ( root ) ;
        }
     
        if ( data < root -> data )
        {
            root -> left = buildtree ( root -> left, data, h ) ;
            /* If left subtree is higher */
    if ( *h )
            {
                switch ( root -> balfact )
                {
                    case 1:
                        node1 = root -> left ;
                        if ( node1 -> balfact == 1 )
                        {
                            printf ( "\nRight rotation along %d.", root -> data ) ;
                            root -> left = node1 -> right ;
                            node1 -> right = root ;
                            root -> balfact = 0 ;
                            root = node1 ;
                        }
                        else
                        {
                            printf ( "\nDouble rotation, left along %d", 
                                                               node1 -> data ) ;
                            node2 = node1 -> right ;
                            node1 -> right = node2 -> left ;
                            printf ( " then right along %d.\n", root -> data ) ;
                            node2 -> left = node1 ;
                            root -> left = node2 -> right ;
                            node2 -> right = root ;
                            if ( node2 -> balfact == 1 )
                                root -> balfact = -1 ;
                            else
                                root -> balfact = 0 ;
                            if ( node2 -> balfact == -1 )
                                node1 -> balfact = 1 ;
                            else
                                node1 -> balfact = 0 ;
                            root = node2 ;
                        }
                        root -> balfact = 0 ;
                        *h = FALSE ;
                        break ;
     
                    case 0:
                        root -> balfact = 1 ;
                        break ;
     
                    case -1:
                        root -> balfact = 0 ;
                        *h = FALSE ;
                }
            }
        }
     
        if ( data > root -> data )
        {
            root -> right = buildtree ( root -> right, data, h ) ;
            /* If the right subtree is higher */
    if ( *h )
            {
                switch ( root -> balfact )
                {
                    case 1:
                        root -> balfact = 0 ;
                        *h = FALSE ;
                        break ;
     
                    case 0:
                        root -> balfact = -1 ;
                        break;
     
                    case -1:
                        node1 = root -> right ;
                        if ( node1 -> balfact == -1 )
                        {
                            printf ( "\nLeft rotation along %d.", root -> data ) ;
                            root -> right = node1 -> left ;
                            node1 -> left = root ;
                            root -> balfact = 0 ;
                            root = node1 ;
                        }
                        else
                        {
                            printf ( "\nDouble rotation, right along %d", 
                                                               node1 -> data ) ;
                            node2 = node1 -> left ;
                            node1 -> left = node2 -> right ;
                            node2 -> right = node1 ;
                            printf ( " then left along %d.\n", root -> data ) ;
                            root -> right = node2 -> left ;
                            node2 -> left = root ;
     
                            if ( node2 -> balfact == -1 )
                                root -> balfact = 1 ;
                            else
                                root -> balfact = 0 ;
                            if ( node2 -> balfact == 1 )
                                node1 -> balfact = -1 ;
                            else
                                node1 -> balfact = 0 ;
                            root = node2 ;
                        }
                        root -> balfact = 0 ;
                        *h = FALSE ;
                }
            }
        }
        return ( root ) ;
    }
     
    /* deletes an item from the tree */
    struct AVLNode * deldata ( struct AVLNode *root, int data, int *h )
    {
        struct AVLNode *node ;
     
        if ( !root )
        {
            printf ( "\nNo such data." ) ;
            return ( root ) ;
        }
        else
        {
            if ( data < root -> data )
            {
                root -> left = deldata ( root -> left, data, h ) ;
                if ( *h )
                    root = balright ( root, h ) ;
            }
            else
            {
                if ( data > root -> data )
                {
                    root -> right = deldata ( root -> right, data, h ) ;
                    if ( *h )
                        root = balleft ( root, h ) ;
                }
                else
                {
                    node = root ;
                    if ( node -> right == NULL )
                    {
                        root = node -> left ;
                        *h = TRUE ;
                        free ( node ) ;
                    }
                    else
                    {
                        if ( node -> left == NULL )
                        {
                            root = node -> right ;
                            *h = TRUE ;
                            free ( node ) ;
                        }
                        else
                        {
                            node -> right = del ( node -> right, node, h ) ;
                            if ( *h )
                                root = balleft ( root, h ) ;
                        }
                    }
                }
            }
        }
        return ( root ) ;
    }
     
    struct AVLNode * del ( struct AVLNode *succ, struct AVLNode *node, int *h )
    {
        struct AVLNode *temp = succ ;
        if ( succ -> left != NULL )
        {
            succ -> left = del ( succ -> left, node, h ) ;
            if ( *h )
                succ = balright ( succ, h ) ;
        }
        else
        {
            temp = succ ;
            node -> data = succ -> data ;
            succ = succ -> right ;
            free ( temp ) ;
            *h = TRUE ;
        }
        return ( succ ) ;
    }
     
    /* balances the tree, if right sub-tree is higher */
    struct AVLNode * balright ( struct AVLNode *root, int *h )
    {
        struct AVLNode *node1, *node2 ;
     
        switch ( root -> balfact )
        {
            case 1:
                root -> balfact = 0 ;
                break;
     
            case 0:
                root -> balfact = -1 ;
                *h  = FALSE ;
                break;
     
            case -1:
                node1 = root -> right ;
                if ( node1 -> balfact <= 0 )
                {
                    printf ( "\nLeft rotation along %d.", root -> data ) ;
                    root -> right = node1 -> left ;
                    node1 -> left = root ;
                    if ( node1 -> balfact == 0 )
                    {
                        root -> balfact = -1 ;
                        node1 -> balfact = 1 ;
                       *h = FALSE ;
                    }
                    else
                    {
                        root -> balfact = node1 -> balfact = 0 ;
                    }
                    root = node1 ;
                }
                else
                {
                    printf ( "\nDouble rotation, right along %d", node1 -> data );
                    node2 = node1 -> left ;
                    node1 -> left = node2 -> right ;
                    node2 -> right = node1 ;
                    printf ( " then left along %d.\n", root -> data );
                    root -> right = node2 -> left ;
                    node2 -> left = root ;
     
                    if ( node2 -> balfact == -1 )
                        root -> balfact = 1 ;
                    else
                        root -> balfact = 0 ;
                    if ( node2 -> balfact == 1 )
                        node1 -> balfact = -1 ;
                    else
                        node1 -> balfact = 0 ;
                    root = node2 ;
                    node2 -> balfact = 0 ;
                }
        }
        return ( root ) ;
    }
     
    /* balances the tree, if left sub-tree is higher */
    struct AVLNode * balleft ( struct AVLNode *root, int *h )
    {
        struct AVLNode *node1, *node2 ;
     
        switch ( root -> balfact )
        {
            case -1:
                root -> balfact = 0 ;
                break ;
     
            case 0:
                root -> balfact = 1 ;
                *h = FALSE ;
                break ;
     
            case 1:
                node1 = root -> left ;
                if ( node1 -> balfact >= 0 )
                {
                    printf ( "\nRight rotation along %d.", root -> data ) ;
                    root -> left = node1 -> right ;
                    node1 -> right = root ;
                    if ( node1 -> balfact == 0 )
                    {
                        root -> balfact = 1 ;
                        node1 -> balfact = -1 ;
                        *h = FALSE ;
                    }
                    else
                    {
                        root -> balfact = node1 -> balfact = 0 ;
                    }
                    root = node1 ;
                }
                else
                {
                    printf ( "\nDouble rotation, left along %d", node1 -> data ) ;
                    node2 = node1 -> right ;
                    node1 -> right = node2 -> left ;
                    node2 -> left = node1 ;
                    printf ( " then right along %d.\n", root -> data ) ;
                    root -> left = node2 -> right ;
                    node2 -> right = root ;
     
                    if ( node2 -> balfact == 1 )
                        root -> balfact = -1 ;
                    else
                        root -> balfact = 0 ;
                    if ( node2-> balfact == -1 )
                        node1 -> balfact = 1 ;
                    else
                        node1 -> balfact = 0 ;
                    root = node2 ;
                    node2 -> balfact = 0 ;
                }
        }
        return ( root ) ;
    }
     
    /* displays the tree in-order */
    void display ( struct AVLNode *root )
    {
        if ( root != NULL )
        {
            display ( root -> left ) ;
            printf ( "%d\t", root -> data ) ;
            display ( root -> right ) ;
        }
    }
     
    /* deletes the tree */
    void deltree ( struct AVLNode *root )
    {
        if ( root != NULL )
        {
            deltree ( root -> left ) ;
            deltree ( root -> right ) ;
        }
        free ( root ) ;
    }
    i want to insert this functions inside the program

    Make Empty
    This operation is for mainly intialization and can be used to destroy entire search tree also.
    Code:
    Tree *make_empty(Tree *t)
    {
      if (t != NULL)
      {
        make_empty(t->left);
        make_empty(t->right);
        free(t);
        t = NULL;
      }
     
      return NULL;
    }
    i want to insert this functions inside the program
    Height
    Finds height of the tree

    Code:
    int height(Tree *t)
    {
      if (t == NULL)
      {
        return -1;
      }
      else
      {
        return t->height;
      }
    }
    i want to insert this functions inside the program

    Find
    This operation returns a Tree node pointer in the search tree that has key X, or returns NULL if there is such node.
    We make a recursive call on sub tree of the tree , either left or right, depending on the relationship of key X to the
    element stored in the tree node
    Code:
    Tree *find(int elem, Tree *t)
    {
      if (t == NULL)
      {
        return NULL;
      }
     
      if (elem < t->element)
      {
        return find(elem, t->left);
      }
      else if (elem > t->element)
      {
        return find(elem, t->right);
      }
      else
      {
        return t;
      }
    }
    i want to insert this functions inside the program

    FindMin
    This operation returns the smallest element node in the tree, i.e. left most element of the tree
    Code:
    Tree *find_min(Tree *t)
    {
      if (t == NULL)
      {
        return NULL;
      }
      else if (t->left == NULL)
      {
        return t;
      }
      else
      {
        return find_min(t->left);
      }
    }
    FindMax
    This operation returns the biggest element node in the tree, i.e. right most element of the tree

    Code:
    Tree *find_max(Tree *t)
    {
      if (t == NULL)
      {
        return NULL;
      }
      else if (t->right == NULL)
      {
        return t;
      }
      else
      {
        return find_max(t->right);
      }
    }
    Insert
    This operation applies a Find operation on the tree, if its found, does nothing., otherwise,
    insert the element at the last spot on the path traversed. After insertion, only nodes that are on the path from the insertion point to the root might have their balance altered because only those nodes have their subtrees altered. As we follow up the path and update the balancing information, we may find a node whose new balance voilates the AVL (balance) condition. We need to rebalance the tree to satisfy AVL property. A violation of the AVL property may occur in four cases: (N is a node to be rebalanced)
    1) An insertion into the left subtree of the left child of the node N
    2) An insertion into the right subtree of the left child of the node N
    3) An insertion into the left subtree of the right child of the node N
    4) An insertion into the right subtree of the right child of the node N
    cases 1 & 4 can be fixed by single rotation
    cases 2 & 3 can be fixed by double rotation
    single and double rotation will be explained after explaing insert and delete operations.
    //Insert i into the tree t, duplicate will be discarded
    //Return a pointer to the resulting tree.



    Code:
    Tree * insert(int value, Tree * t)
    {
      Tree * new_node;
      if (t == NULL)
      {
        new_node = (Tree *) malloc (sizeof (Tree));
        if (new_node == NULL)
        {
                return t;
        }
     
        new_node->element = value;
        new_node->height = 0;
        new_node->left = new_node->right = NULL;
        return new_node;
      }
      else if (value < t->element)
      {
        t->left = insert(value, t->left);
        if (height(t->left) - height(t->right) == 2)
        {
          if (value < t->left->element)
          {
            t = single_rotation_with_left(t);
          }
          else
          {
            t = double_rotation_with_left(t);
          }
        }
      }
      else if (value > t->element)
      {
        t->right = insert(value, t->right);
        if (height(t->right) - height(t->left) == 2)
        {
          if (value > t->right->element)
          {
            t = single_rotation_with_right(t);
          }
          else
          {
            t = double_rotation_with_right(t);
          }
        }
       }
      //else duplicate, ignore it
     
      t->height = MAX(height(t->left), height(t->right)) + 1;
      return t;
    }



    i had a hard time to find the COMPARE function ... which make this code incomplete! ...

    if someone can insert the remaining functions that i listed above please help...

    lastly ... can someone provide or add COMPARE function! ...

    thanks in advance ... it gives me a headache with this project!

    thank you!
    Last edited by trojan32; 01-26-2013 at 10:30 PM.

  2. #2
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    472
    You clearly didn't write any of this code, nor do you understand any of it, nor do you even understand what it is you are asking us to do or trying to do.

    So please accept that you are going to fail whatever test/class this is for and move on. Next time DO THE COURSEWORK and READ THE MATERIAL. This is an obvious cry for free code and it's really quite insulting...you're lucky you're even getting a response at all.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    It seems it came from here (indentation perfect copy)
    Program to maintain an AVL tree - C Programming Examples and Tutorials

    i want to insert this functions inside the program

    Make Empty
    This operation is for mainly intialization and can be used to destroy entire search tree also.
    What does "I want to insert" even mean?
    You've managed to get the hang of copy/paste to a forum, why can't you do the same in your source code editor.

    Just paste the code, press save, press compile.

    Of course, as nonpuz says, starting with your OWN code would be a bonus.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Jan 2013
    Posts
    2
    Quote Originally Posted by Salem View Post
    It seems it came from here (indentation perfect copy)
    Program to maintain an AVL tree - C Programming Examples and Tutorials


    What does "I want to insert" even mean?
    You've managed to get the hang of copy/paste to a forum, why can't you do the same in your source code editor.

    Just paste the code, press save, press compile.

    Of course, as nonpuz says, starting with your OWN code would be a bonus.
    -----------------------------------------------------------------

    ive already done with all the functions i listed above ...
    *empty
    *max
    *min
    *insert
    *delete



    but in compare function ... cant figure it out where to start which the program automatically balanced the trees! ...

    i want to find the simpliest code because we have to compute for the the run time! and i have a doubt with my code which already done! but i have to find the smallest running time!

    i left with the compare function!... got no idea!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Auto-Complete Program HELP
    By YannB in forum C Programming
    Replies: 13
    Last Post: 01-20-2013, 02:16 PM
  2. Auto-Complete Program in c
    By YannB in forum C Programming
    Replies: 9
    Last Post: 01-15-2013, 12:01 AM
  3. Little help to complete my program..pls..
    By scorpio76 in forum C Programming
    Replies: 14
    Last Post: 02-24-2011, 04:58 AM
  4. c++ complete program
    By gaza rose in forum C++ Programming
    Replies: 7
    Last Post: 12-11-2008, 12:47 PM
  5. How to complete program. Any probs now?
    By stehigs321 in forum C Programming
    Replies: 7
    Last Post: 11-19-2003, 03:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21