c - 从树中删除节点函数在 C 中不起作用

Question

我必须从树中消除一个节点。我首先尝试消除节点根，这样我就不必搜索节点并且它可以工作。但后来我尝试通过搜索来做到这一点，当函数调用自身时，程序在通过第一个 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;
}*

Answer 1

正如 Nick 建议的那样，您应该检查 tree 在 Eliminar 开头是否有效。但是，如果第一个 if 语句执行正常，则 tree 不能为 NULL。不过， tree->der 可以 - 您也应该在取消引用之前检查它。当然，第一个 if 中的 tree->izq 也是如此 - 只是因为它在您第一次调用此函数时不为 NULL，所以不要假设它永远不会。

一些进一步的说明:您正在 Elimar 中搜索具有值 valor 的节点(因此这是一个坏名字 - 您并没有消除那里的节点，仅将其标记为以后删除)。

如果找到它，则没有必要继续搜索，因此您可以立即从两个 if 分支返回。

此外，通过设置 left 或 right 标志，可以单独处理在左子树或右子树中找到 valor 的情况，并相应地调用Eliminarleft或Eliminarright。直接存储要删除的左子树或右子树会更简单，因此您可以删除两个标志和两个删除方法:

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);
}