0

ツリーからノードを削除する必要があります。最初にノードのルートを削除しようとしたため、ノードを検索する必要がなく、機能します。しかし、検索してそれをやろうとしたところ、関数が自分自身を呼び出すと、最初のifステートメントを通過した後にプログラムがフリーズします...

問題は関数にありますvoid Eliminar(struct arbol *tree, int valor);:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct arbol
{
    int numero;
    struct arbol *izq;
    struct arbol *der;
};
struct arbol *raiz = NULL;
struct arbol *eliminador = NULL;
int encontrado = 0;
int right = 0, left = 0;
int crear_arbol(int dato);
struct arbol * crear_nodo(int valor);
void ImprimeDNI (struct arbol *tree);
void ImprimeIND (struct arbol *tree);
void ImprimeNDI (struct arbol *tree);
void Buscar (struct arbol *tree, int valor);
void Eliminar (struct arbol *tree,int valor);
int Eliminaroot ();
int Eliminarright(struct arbol *localizador);
int Eliminarleft(struct arbol *localizador);
int main ()
{
    int n, i;
    char opcion;
    int numero;
    puts("Ingrese la cantidad de numeros a ingresar");
    scanf("%d", &n);
    int numeros[n];
    puts("Ingrese los numeros separados por espacio o enter");
    for(i = 0; i < n; i++)
    {
        scanf("%d",&numeros[i]);
    }
    for(i = 0; i < n; i++)
    {
        crear_arbol(numeros[i]);
    }
    puts("");
    system("pause");
    system("cls");
    do
    {
        encontrado = 0;
        puts("******** OPCIONES ********");
        puts("|B o b| Para buscar un numero");
        puts("|E o e| Eliminar un nodo");
        puts("|I o i| Imprimir de las 3 formas principales");
        fflush(stdin);
        opcion = getch();
        switch(opcion)
        {
        case 'B': case 'b': puts("Ingrese el numero a buscar"); scanf("%d",&numero); Buscar(raiz,numero);
        if(encontrado == 0) {puts("El numero no esta en el arbol");} break;
        case 'E': case 'e': puts("Ingrese el numero a eliminar"); scanf("%d", &numero);
        if(raiz->numero == numero)
        {
            Eliminaroot();
        }
        else
        {
            Eliminar(raiz,numero);
            if(right == 0 && left == 0)
            {
                puts("No se encontro el numero");
            }
            if(right == 1)
            {
                Eliminarright(eliminador);
            }
            if(left == 1)
            {
                Eliminarleft(eliminador);
            }
        }
        break;
        case 'I': case 'i': ImprimeDNI(raiz); puts(""); ImprimeIND(raiz); puts(""); ImprimeNDI(raiz); puts(""); break;
        default: puts("Opcion Invalida"); break;
        }
        puts("");
        system("pause");
        system("cls");
    }while (opcion != 'T' || opcion != 't');
    return 0;
}
int crear_arbol(int dato)
{
    struct arbol *recorrer = raiz;
    struct arbol *nuevo;
    if(raiz == NULL)
    {
        raiz = crear_nodo(dato);
        return 1;
    }
    else
    {
        nuevo = crear_nodo(dato);
    }
    while (1) {
        if(recorrer->numero <= nuevo->numero)
        {
            if(recorrer->der == NULL)//si las ramas de donde esta el puntero que recorre son NULL, significa
            { //que es la ultima comparacion
                recorrer->der = nuevo;
                break;
            }
            recorrer = recorrer->der;
        }
        else
        {
            if(recorrer->izq == NULL)//lo mismo que el if de arriba
            {
                recorrer->izq = nuevo;
                break;
            }
            recorrer = recorrer->izq;
        }
    }//while
    return 1;
}
struct arbol * crear_nodo(int valor)
{
    struct arbol *aux;
    aux = (struct arbol*)malloc(sizeof(struct arbol));
    aux->numero = valor;
    aux->izq = NULL;
    aux->der = NULL;
    return aux;
}
void ImprimeDNI (struct arbol *tree)
{
    if(!tree)
        return;
    ImprimeDNI(tree->der);
    printf("%d, ", tree->numero);
    ImprimeDNI(tree->izq);
}
void ImprimeIND (struct arbol *tree)
{
    if(!tree)
        return;
    ImprimeIND(tree->izq);
    printf("%d, ", tree->numero);
    ImprimeIND(tree->der);
}
void ImprimeNDI (struct arbol *tree)
{
    if(!tree)
        return;
    printf("%d, ", tree->numero);
    ImprimeNDI(tree->der);
    ImprimeNDI(tree->izq);
}
void Buscar (struct arbol *tree, int valor)
{
    if(tree->numero == valor)
    {printf("El numero si se encuentra en el arbol"); encontrado = 1;}
    if(!tree)
        return;
    Buscar(tree->der, valor);
    Buscar(tree->izq,valor);
}
int Eliminaroot ()
{
    int encontrado = 0;
    struct arbol *aux = raiz;
    struct arbol *buscador = raiz->der;
    for(; buscador->der != NULL ; buscador = buscador->der)
    {
        if(buscador->izq != NULL)
        {
            encontrado = 1;
        for(; buscador->izq->izq != NULL ; buscador = buscador->izq)
        {
        }
        break;
        }//if
    }
    if(encontrado == 0)
    {
        if(raiz->der == NULL)
        {
            raiz = aux->izq;
            raiz->izq = aux->izq->izq;
            raiz->der = aux->izq->der;
        }
        else
        {
        raiz = aux->der;
        raiz->izq = aux->izq;
        raiz->der = aux->der->der;
        free(aux);
        }
    }
    else
    {
    raiz = buscador->izq;
    raiz->der = aux->der;
    raiz->izq = aux->izq;
    buscador->izq = NULL;
    free(aux);
    }
    return 1;
}
void Eliminar (struct arbol *tree, int valor)
{
    if(tree->izq->numero == valor)
    {
        eliminador = tree;
        left = 1;
    }
    puts("AAAA");
    if(tree->der->numero == valor)
    {
        eliminador = tree;
        right = 1;
    }
    if(!tree)
        return;
    Eliminar(tree->der, valor);
    Eliminar(tree->izq, valor);
}
int Eliminarright(struct arbol *localizador)
{
    return 1;
}
int Eliminarleft(struct arbol *localizador)
{
    return 1;
}*
4

3 に答える 3

1

Nickが提案したようtreeに、の先頭でそれが有効であることを確認する必要がありEliminarます。ただし、最初のifステートメントが正常に実行される場合は、treeできませんNULL。tree->derただし、間接参照する前にそれも確認する必要があります。そしてもちろん、tree->izq最初の場合も同じです。この関数を初めて呼び出すときにNULLではないという理由だけで、決してそうなるとは思わないでください。

valorさらにいくつかの注意事項：値がであるノードを検索していますEliminar（したがって、これは不適切な名前です。ノードを削除するのではなく、後で削除するためにマークを付けるだけです）。

見つけたら検索を続ける意味がないので、returnすぐに両方のifブランチから離れることができます。

さらに、またはフラグを設定し、それに応じてまたはを呼び出すことvalorにより、左または右のサブツリーで見つかった場合を個別に処理します。削除する左または右のサブツリーを直接保存する方がはるかに簡単なので、2つのフラグと2つの削除方法を削除できます。leftrightEliminarleftEliminarright

void Eliminar (struct arbol *tree, int valor)
{
    if(!tree)
        return;
    if(tree->izq && tree->izq->numero == valor)
    {
        eliminador = tree->izq;
        return;
    }
    puts("AAAA");
    if(tree->der && tree->der->numero == valor)
    {
        eliminador = tree->der;
        return;
    }
    Eliminar(tree->der, valor);
    Eliminar(tree->izq, valor);
}

...
Eliminar(raiz,numero);
if(!eliminador)
{
    puts("No se encontro el numero");
}
else
{
    Eliminar(eliminador);
}

これはよりクリーンですが、さらに先に進むことができます。の左右のサブツリーをチェックしてEliminarから、同じサブツリーを繰り返していることに注意してください。代わりにtree、それ自体だけをチェックしてから、再帰するだけで十分です。

void Eliminar (struct arbol *tree, int valor)
{
    if(!tree)
        return;
    if(tree->numero == valor)
    {
        eliminador = tree;
        return;
    }
    puts("AAAA");
    Eliminar(tree->der, valor);
    Eliminar(tree->izq, valor);
}
于 2012-04-06T07:46:45.313 に答える
0

関数の先頭にあるポインターをチェックしていないtreeため、null ポインターでアクセス違反が発生している可能性があります。if (!tree) return;チェックを関数の一番上に移動します。

于 2012-04-06T07:43:07.143 に答える