dimanche 28 juin 2015

Access Violation error. AVL TREE during insertion. C

So I got an AVL tree online for a project. and I am trying to insert elements with a loop to see if it works. obviously its not working. am getting an access violation error.

here is the tree. the code is long. I know. but I can tell you that its in the insert function not the others

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

#define FALSE 0
#define TRUE 1




MY_TREE deldata(MY_TREE pRoot, int, int *);
MY_TREE delete_node(MY_TREE pRoot, MY_TREE hNode, int *);
Node_ptr balright(Node_ptr pRoot, int *);
Node_ptr balleft(Node_ptr pRoot, int *);
void display(MY_TREE pRoot);
void tree_destroy(MY_TREE pRoot);
Node_ptr  balleft(Node_ptr pRoot, int *h);
MY_TREE insert(MY_TREE hRoot, int data, int *h);
void init_tree_functions(Node_ptr pRoot);


struct node
{


    MY_TREE(*deldata)(MY_TREE pRoot, int, int *);
    void(*display)(MY_TREE pRoot);
    void(*tree_destroy)(MY_TREE pRoot);
    MY_TREE(*insert)(MY_TREE hRoot, int data, int *h);



    int data;
    int balfact;
    Node_ptr left;
    Node_ptr right;
};


void init_tree_functions(Node_ptr pRoot){

    pRoot->tree_destroy = tree_destroy;
    pRoot->deldata = deldata;
    pRoot->display = display;
    pRoot->insert = insert;


}


//MY_TREE my_tree_init_default(){
//
//  Node_ptr pRoot;
//
//  pRoot =(Node_ptr) malloc(sizeof(Node));
//  
//  if (pRoot == NULL){
//
//      printf("Bad stuff \n"); 
//
//      exit(1);
//  }
//
//  pRoot->left = NULL;
//  pRoot->right = NULL;
//  pRoot->data = NULL;
//  pRoot->balfact = 0;
//  init_tree_functions(pRoot);
//
//  
//
//  return (MY_TREE)pRoot;
//
//}

MY_TREE insert(MY_TREE hRoot, int data, int *h)
{
    Node_ptr  node1, node2;
    Node_ptr pRoot = (Node_ptr)hRoot;



    if (pRoot==NULL)
    {
        pRoot = (Node_ptr) malloc(sizeof(Node));



        pRoot->data = data;
        pRoot->left = NULL;
        pRoot->right = NULL;
        pRoot->balfact = 0;
        *h = TRUE;



        return ((MY_TREE)pRoot);
    }

    if (data < pRoot->data)
    {
        pRoot->left = insert((MY_TREE)pRoot->left, data, h);

        if (*h)
        {
            switch (pRoot->balfact)
            {
            case 1:
                node1 = pRoot->left;
                if (node1->balfact == 1)
                {

                    pRoot->left = node1->right;
                    node1->right = pRoot;
                    pRoot->balfact = 0;
                    pRoot = node1;
                }
                else
                {

                    node2 = node1->right;
                    node1->right = node2->left;

                    node2->left = node1;
                    pRoot->left = node2->right;
                    node2->right = pRoot;
                    if (node2->balfact == 1)
                        pRoot->balfact = -1;
                    else
                        pRoot->balfact = 0;
                    if (node2->balfact == -1)
                        node1->balfact = 1;
                    else
                        node1->balfact = 0;
                    pRoot = node2;
                }
                pRoot->balfact = 0;
                *h = FALSE;
                break;

            case 0:
                pRoot->balfact = 1;
                break;

            case -1:
                pRoot->balfact = 0;
                *h = FALSE;
            }
        }
    }

    if (data > pRoot->data)
    {
        pRoot->right = insert((MY_TREE)pRoot->right, data, h);

        if (*h)
        {
            switch (pRoot->balfact)
            {
            case 1:
                pRoot->balfact = 0;
                *h = FALSE;
                break;

            case 0:
                pRoot->balfact = -1;
                break;

            case -1:
                node1 = pRoot->right;
                if (node1->balfact == -1)
                {

                    pRoot->right = node1->left;
                    node1->left = pRoot;
                    pRoot->balfact = 0;
                    pRoot = node1;
                }
                else
                {

                    node2 = node1->left;
                    node1->left = node2->right;
                    node2->right = node1;

                    pRoot->right = node2->left;
                    node2->left = pRoot;

                    if (node2->balfact == -1)
                        pRoot->balfact = 1;
                    else
                        pRoot->balfact = 0;
                    if (node2->balfact == 1)
                        node1->balfact = -1;
                    else
                        node1->balfact = 0;
                    pRoot = node2;
                }
                pRoot->balfact = 0;
                *h = FALSE;
            }
        }
    }

    return ((MY_TREE)pRoot);
}


MY_TREE deldata(MY_TREE hRoot, int data, int *h)
{
    Node_ptr pRoot = (Node_ptr)hRoot;
    Node_ptr node;

    if (!pRoot)
    {

        return (pRoot);
    }
    else
    {
        if (data < pRoot->data)
        {
            pRoot->left = deldata((MY_TREE)pRoot->left, data, h);
            if (*h)
                pRoot = balright(pRoot, h);
        }
        else
        {
            if (data > pRoot->data)
            {
                pRoot->right = deldata((MY_TREE)pRoot->right, data, h);
                if (*h)
                    pRoot = balleft(pRoot, h);
            }
            else
            {
                node = pRoot;
                if (node->right == NULL)
                {
                    pRoot = node->left;
                    *h = TRUE;
                    free(node);
                }
                else
                {
                    if (node->left == NULL)
                    {
                        pRoot = node->right;
                        *h = TRUE;
                        free(node);
                    }
                    else
                    {
                        node->right = delete_node((MY_TREE)node->right, node, h);
                        if (*h)
                            pRoot = balleft(pRoot, h);
                    }
                }
            }
        }
    }
    return ((MY_TREE)pRoot);
}

MY_TREE  delete_node(MY_TREE hSucc, MY_TREE hNode, int *h)
{

    Node_ptr node = (Node_ptr)hNode;
    Node_ptr succ = (Node_ptr)hSucc;

    Node_ptr temp = succ;
    if (succ->left != NULL)
    {
        succ->left = delete_node((MY_TREE)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 ((MY_TREE)succ);
}


Node_ptr balright(Node_ptr pRoot , int *h)
{
    Node_ptr node1, node2;

    switch (pRoot->balfact)
    {
    case 1:
        pRoot->balfact = 0;
        break;

    case 0:
        pRoot->balfact = -1;
        *h = FALSE;
        break;

    case -1:
        node1 = pRoot->right;
        if (node1->balfact <= 0)
        {

            pRoot->right = node1->left;
            node1->left = pRoot;
            if (node1->balfact == 0)
            {
                pRoot->balfact = -1;
                node1->balfact = 1;
                *h = FALSE;
            }
            else
            {
                pRoot->balfact = node1->balfact = 0;
            }
            pRoot = node1;
        }
        else
        {

            node2 = node1->left;
            node1->left = node2->right;
            node2->right = node1;

            pRoot->right = node2->left;
            node2->left = pRoot;

            if (node2->balfact == -1)
                pRoot->balfact = 1;
            else
                pRoot->balfact = 0;
            if (node2->balfact == 1)
                node1->balfact = -1;
            else
                node1->balfact = 0;
            pRoot = node2;
            node2->balfact = 0;
        }
    }
    return (pRoot);
}


Node_ptr  balleft(Node_ptr pRoot, int *h)
{
    Node_ptr  node1, node2;

    switch (pRoot->balfact)
    {
    case -1:
        pRoot->balfact = 0;
        break;

    case 0:
        pRoot->balfact = 1;
        *h = FALSE;
        break;

    case 1:
        node1 = pRoot->left;
        if (node1->balfact >= 0)
        {

            pRoot->left = node1->right;
            node1->right = pRoot;
            if (node1->balfact == 0)
            {
                pRoot->balfact = 1;
                node1->balfact = -1;
                *h = FALSE;
            }
            else
            {
                pRoot->balfact = node1->balfact = 0;
            }
            pRoot = node1;
        }
        else
        {

            node2 = node1->right;
            node1->right = node2->left;
            node2->left = node1;

            pRoot->left = node2->right;
            node2->right = pRoot;

            if (node2->balfact == 1)
                pRoot->balfact = -1;
            else
                pRoot->balfact = 0;
            if (node2->balfact == -1)
                node1->balfact = 1;
            else
                node1->balfact = 0;
            pRoot = node2;
            node2->balfact = 0;
        }
    }
    return (pRoot);
}


void display(MY_TREE hRoot)
{

    Node_ptr pRoot = (Node_ptr)hRoot;
    if (pRoot != NULL)
    {
        display(pRoot->left);
        printf("%d\t", pRoot->data);
        display(pRoot->right);
    }
}


void tree_destroy(MY_TREE hRoot)
{
    Node_ptr pRoot = (Node_ptr)hRoot;
    if (pRoot != NULL)
    {
        tree_destroy(pRoot->left);
        tree_destroy(pRoot->right);
    }
    free(pRoot);
}

this is the loop I have.

MY_TREE pRoot=NULL;

//pRoot = my_tree_init_default();



for (i = 0;  i < 99; i++){
    number = i;
    pRoot=pRoot->insert(pRoot, number, pResult);
    printf("a");


}

its crashing before 1 element is added. however when I do the init function. 1 element is added before it crashes. I think it has to do with the function pointers.

Aucun commentaire:

Enregistrer un commentaire