从树中消除节点功能在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

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

Answer 2

由于尼克建议，你应该检查tree是否在Eliminar开始有效。但是，如果第一个if语句执行正常，tree不能为NULL。 tree->der可以 - 但你应该在提取它之前检查它。当然，第一个if中的tree->izq也是如此 - 仅仅因为它在第一次调用这个函数时不是NULL，不要认为它永远不会。

还有一些注意事项：您正在搜索Eliminar中的值为valor的节点（因此这是一个糟糕的名称 - 您并未消除该节点，仅将其标记为稍后删除）。

如果你发现它，没有一点继续搜索，所以你可以从if分支机构立即return。

此外，当您发现在左或右子树valor，通过设置left或right标志，并呼吁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); 
} 

Answer 3

@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);来更新根节点并获取成功/失败指示符。