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

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

进一步说明：您正在搜索具有 in 值的节点valor（Eliminar因此这是一个坏名字 - 您没有消除那里的节点，只是将其标记为以后删除）。

如果找到它，继续搜索就没有意义了，因此您可以return立即从两个if分支中搜索。

此外，当您valor在左子树或右子树中找到时，您可以通过设置leftorright标志并相应地调用Eliminarleftor来分别处理这些情况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);
}
于 2012-04-06T07:46:45.313 回答
0

您没有检查tree函数顶部的指针，因此可能会导致空指针访问冲突。将您的if (!tree) return;支票移动到函数的顶部。

于 2012-04-06T07:43:07.143 回答
0

@PéterTörök 的回答让您成为其中的一部分。在我看来，您有一个标准的二叉树设置，左侧为“值小于”，右侧为“值大于”（或者如果您允许重复，则可能 >=）。

不过，摆脱全局变量（Eliminar集合eliminador和左/右标志）会非常好，您可以通过使用指向指针的指针来做到这一点。它可以获取指向树节点的指针，而不是Eliminar获取树节点，并在删除节点时更新它。此外，删除节点后，您可以停止：

int Eliminar(struct arbol **tree_p, int valor)
{
    struct arbol *tree = *tree_p;

    if (!tree)
        return 0; /* nothing to remove */ 
    if (tree->numero == valor) {
        /* this is the node to remove */
        *tree_p = rewrite(tree); /* rewrite subtree from here down, and update */
        return 1; /* indicate that we're done */
    }
    /* didn't find the node to remove ... use left or right subtree for next attempt */
    tree_p = tree->numero > valor ? &tree->der : &tree->izq;
    return Eliminar(tree_p, valor);
}

（不确定我上面的左/右是否正确；我把它留给你处理:-)）。

现在很容易将递归变成迭代。困难的部分是rewrite()，因为您可以同时拥有 的左右子树tree。如果你只有一个，这很容易，但如果你有两个，那就不那么容易了。再次，我把它作为练习...... :-)

您可以Eliminar返回实际删除的树节点（或者NULL如果valor不在树中）；这在某些情况下可能很有用。在任何一种情况下，您只需执行以下操作：result = Eliminar(&root, valor);更新根节点并获取成功/失败指示器。

于 2012-04-06T08:35:04.147 回答