Estoy tratando de implementar una función que debería agregar un valor en la hoja, aquí mis códigos

Estructura del nodo: el nodo contiene dos, el escudo, el izquierdo y el derecho, y su papá (predecesor) y el valor.

struct arbre {
int val ;
struct arbre * D;
struct arbre * G ;
struct arbre * pere ;
};

Aquí está la función: la función siempre agrega el valor en las hojas

void ajout_feuille( struct arbre** arbre , int value )
{
    struct arbre* q ,*p ;
    if ( *arbre == NULL)
    {
        q=malloc(sizeof(struct arbre ));
        q->D=NULL ;
        q->G=NULL;
        q->pere=NULL;
        q->val=value;
        *arbre=q ;
    }
    else
    {
    p=*arbre;
    while(p!=NULL)
    {
        if (p->val<value) //if the value is > we go on the right shild;
        {
            if (p->D==NULL) // if we are on the leaf 
            {
                q=malloc(sizeof(struct arbre ));
                q->val=value;
                q->D=NULL;
                q->G=NULL;
                q->pere=p;
                p->D=q;
            }else
            {
                p=p->D;
            }

        }else
        {
            if (p->val>value)
            {
                if(p->G==NULL)
                {
                     q=malloc(sizeof(struct arbre ));
                     q->val=value;
                     q->D=NULL;
                     q->G=NULL;
                     q->pere=p;
                     p->G=q;
                }
            }else { p=p->G; }
        }
    }
    }

}

Aquí está el método de visualización: este es el método de visualización de prefijo

void affichage (struct arbre * arbre )
{
    if (arbre != NULL){
printf("%d\n",arbre->val);
    affichage(arbre->G);
    affichage(arbre->D);

}
}

Este es el método principal:

int main()
{
    struct arbre * A=NULL ;

    ajout_feuille(&A,5);
    ajout_feuille(&A,4);
    affichage(A);


    return 0;
}

El problema es: el método de visualización no muestra nada, creo que hay un problema en los punteros.

-2
Hįś Mãjĕštý 22 nov. 2019 a las 23:00

1 respuesta

La mejor respuesta

Más punteros y variables en el mismo no hacen que el código sea más fácil de leer. La razón por la que no se imprime nada es porque su ciclo de enumeración nunca termina.

Su código tiene dos problemas de bucle infinito de código. Recuerde, no tiene declaraciones break en este código, por lo que lo único que desencadena ese bucle while es cuando p se vuelve NULL.

  • Un recorrido final del lado izquierdo nunca saldrá del bucle
  • Las entradas duplicadas nunca saldrán del ciclo

Con respecto al primero de estos, perseguir un cruce del lado izquierdo nunca establecerá p en NULL debido a lo siguiente. Considere la diferencia entre su recorrido del lado derecho y su recorrido del lado izquierdo.

Un recorrido del lado derecho hace esto:

        if (p->val<value) //if the value is >, we go on the right child;
        {
            if (p->D==NULL) // if we are on the leaf
            {
                q=malloc(sizeof(struct arbre ));
                q->val=value;
                q->D=NULL;
                q->G=NULL;
                q->pere=p;
                p->D=q;
            }
            else
            {
                p=p->D;
            }
        }

Tenga en cuenta específicamente a qué se articula la reacción else p=p->D. Ahora mire su lógica del lado izquierdo, que debería ser similar, pero persiguiendo un puntero diferente usando lógica inversa (que es un error que eventualmente conduce a su problema de bucle infinito en el caso de inserción duplicada, pero llegaremos a eso en un momento):

        if (p->val>value) // ok so far
        {
            if(p->G==NULL)
            {
                q=malloc(sizeof(struct arbre ));
                q->val=value;
                q->D=NULL;
                q->G=NULL;
                q->pere=p;
                p->G=q;
            }
        }
        else
        {
            p=p->G;
        }

Observe dónde cuelga ahora la condición else. Primero, es incorrecto, segundo, que if y else realmente no debería estar allí en primer lugar a menos que esté tratando específicamente de construir un conjunto (es decir, sin claves duplicadas), y si ese es el En este caso, aún necesita una cláusula de salida para romper el estado while(p!=NULL) que de otro modo sería interminable.

Las versiones completamente funcionales de su código que (a) no permiten duplicados, a los que parece estar apuntando, y (b) permiten duplicados, se encuentran a continuación. A continuación, se ofrece una alternativa que le recomiendo encarecidamente que la revise.

Solución n. ° 1: sin duplicados

void ajout_feuille0( struct arbre** arbre , int value )
{
    struct arbre* q ,*p ;
    if ( *arbre == NULL)
    {
        q=malloc(sizeof(struct arbre ));
        q->D=NULL ;
        q->G=NULL;
        q->pere=NULL;
        q->val=value;
        *arbre=q ;
    }
    else
    {
        p = *arbre;
        while (p!=NULL)
        {
            if (p->val<value) //if the value is > we go on the right shild;
            {
                if (p->D==NULL) // if we are on the leaf
                {
                    q=malloc(sizeof(struct arbre ));
                    q->val=value;
                    q->D=NULL;
                    q->G=NULL;
                    q->pere=p;
                    p->D=q;
                }
                else
                {
                    p=p->D;
                }
            }
            else if (value < p->val) // else if less we go down the left side.
            {
                if(p->G==NULL)
                {
                    q=malloc(sizeof(struct arbre ));
                    q->val=value;
                    q->D=NULL;
                    q->G=NULL;
                    q->pere=p;
                    p->G=q;
                }
                else
                {
                    p=p->G;
                }
            }
            else // else the value is already in the tree.
            {
                break;
            }
        }
    }
}

Solución n. ° 2: duplicados permitidos

void ajout_feuille0( struct arbre** arbre , int value )
{
    struct arbre* q ,*p ;
    if ( *arbre == NULL)
    {
        q=malloc(sizeof(struct arbre ));
        q->D=NULL ;
        q->G=NULL;
        q->pere=NULL;
        q->val=value;
        *arbre=q ;
    }
    else
    {
        p = *arbre;
        while (p!=NULL)
        {
            if (p->val<value) //if the value is > we go on the right shild;
            {
                if (p->D==NULL) // if we are on the leaf
                {
                    q=malloc(sizeof(struct arbre ));
                    q->val=value;
                    q->D=NULL;
                    q->G=NULL;
                    q->pere=p;
                    p->D=q;
                }
                else
                {
                    p=p->D;
                }
            }
            else
            {
                if(p->G==NULL)
                {
                    q=malloc(sizeof(struct arbre ));
                    q->val=value;
                    q->D=NULL;
                    q->G=NULL;
                    q->pere=p;
                    p->G=q;
                }
                else
                {
                    p=p->G;
                }
            }
        }
    }
}

Alternativa

La verdad es que no necesitas p y q. Solo necesitas dos cosas:

  1. El puntero a puntero que le dieron. Podemos usar eso para atravesar el árbol dirigiéndonos directamente a cada puntero durante el descenso.
  2. un puntero "padre" de retroceso, inicialmente establecido en NULL, y establecido en el puntero del nodo actual antes de descender por el siguiente hijo.

Al usarlos, puede implementar ambos algoritmos (no duplicados y permitir duplicados) de manera mucho más concisa:

Sin duplicados

void ajout_feuille( struct arbre** tree , int value )
{
    struct arbre *pere = NULL;
    while (*tree)
    {
        pere = *tree;

        // left side ?
        if (value < (*tree)->val)
            tree = &(*tree)->G;

        // right side ?
        else if ((*tree)->val < value)
            tree = &(*tree)->D;

        else // duplicate found
            break;
    }

    if (!*tree) // null means we have a place to hang a node.
    {
        *tree = malloc(sizeof **tree);
        if (!*tree)
        {
            perror("Failed to allocate new tree node");
            exit(EXIT_FAILURE);
        }

        (*tree)->val = value;
        (*tree)->pere = pere;
        (*tree)->G = NULL;
        (*tree)->D = NULL;
    }
}

Permitir duplicados

void ajout_feuille( struct arbre** tree , int value )
{
    struct arbre *pere = NULL;
    while (*tree)
    {
        pere = *tree;

        // left side ?
        if (value < (*tree)->val)
            tree = &(*tree)->G;

        // els ejust move to right
        else tree = &(*tree)->D;
    }

    if (!*tree) // null means we have a place to hang a node.
    {
        *tree = malloc(sizeof **tree);
        if (!*tree)
        {
            perror("Failed to allocate new tree node");
            exit(EXIT_FAILURE);
        }

        (*tree)->val = value;
        (*tree)->pere = pere;
        (*tree)->G = NULL;
        (*tree)->D = NULL;
    }
}

En ambos casos, el código es mucho más limpio y evita el bucle adicional a través del while externo.

Espero que ayude.

1
WhozCraig 22 nov. 2019 a las 22:02