Cノードでツリーのノード機能を削除できない

Question

ツリーからノードを削除する必要があります。最初にノードのルートを削除しようとしたので、ノードを検索する必要はなく、動作します。しかし、その後、私は検索して、それを実行しようとしました、そして関数が自分自身を呼び出すとき、プログラムがvoid Eliminar(struct arbol *tree, int valor);、

問題が関数である...それはif文最初の通過した後にフリーズ：

#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

Nickが示唆したように、がEliminarの冒頭に有効であることを確認する必要があります。ただし、最初のif文が正常に実行された場合、treeはNULLにはなりません。 tree->derでも、逆参照する前にチェックする必要があります。もちろん、初めての場合はtree->izqと同じです。この関数を初めて呼び出すときにはNULLではないからです。

valorの値を持つノードを検索しています（これは悪い名前です - ノードを削除しておらず、後で削除するためにマークするだけです）。

見つけた場合は、検索を続けることはありませんので、すぐにreturnの両方の枝からifの枝にすることができます。あなたがleftやrightフラグを設定し、それに応じてEliminarleftまたはEliminarrightを呼び出すことによって、左または右のサブツリーにvalorを見つけたとき

はまた、あなたが別途ケースを扱います。

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

これはきれいですが、我々はさらに行くことができます：そう、あなたは二つのフラグと2つの除去方法をドロップすることができ、直接削除する左または右のサブツリーを格納するためにはるかに簡単になります。左右のサブツリーをEliminarにチェックインしてから、同じサブツリーを再帰的に調べていることに注目してください。その後、再帰、唯一tree自体をチェックする代わりにすれば良い：PéterTörökの答え@

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

はあなたが道の一部を取得します。それは、私は、あなたが "値よりも小さい"と "値より大きい"（または重複を許可する場合はおそらく> =）で標準バイナリツリーの設定を持っているように見えます。

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

（Iは、上記右の正しい/左しまったかどうかわからない、あなたが:-)上で動作するために私がいることを残します）。

再帰を繰り返し実行するのは簡単です。難しい部分はrewrite()です。なぜなら、左右のサブツリーの両方をtreeにすることができるからです。あなたは1つだけ持っているなら、それは簡単ですが、もしあなたが両方を持っているなら、これはもう簡単ではありません。繰り返しますが、私はそれを練習として残します:-)

Eliminarは、実際に削除されたツリーノード（またはNULLの場合はvalorがツリーにない場合）を返します。いくつかの場合に役立つ可能性があります。いずれの場合も、result = Eliminar(&root, valor);を実行してルートノードを更新し、成功/失敗インジケータを取得します。