[C] - Eliminazione nodo albero binario.

[Saetta93]

Ciao a tuttii :D

Io ho questo codice, devo completare la/le funzione/i per eliminare un nodo da un albero binario, ma sono ad un punto in cui non riesco a continuare..

In pratica all'interno di questo if (da quello che ho capito):

if((*p)->ptrsx == NULL)
{
num = (*p)->dato;
free(*p);
*p=NULL;
risultato=num;
}

dovrei salvare il contenuto della foglia, nel puntatore del nodo appena eliminato.. ma come devo fare? :confused:

Qualcuno può aiutarmi gentilmente? :)

Codice C:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
int dato;
struct nodo *ptrsx;
struct nodo *ptrdx;
}nodo;

int elimina(nodo** );

nodo* creazione(){
nodo *q;
q = malloc(sizeof(nodo));

printf("\nInserisci un numero intero:\t");
scanf("%i", &q->dato);
printf("\n");

q->ptrsx = NULL;
q->ptrdx = NULL;

return q;
}

void ins_ord(nodo *p,nodo *q)
{
nodo *r;
r = p;
if(r->dato > q->dato) {
if(r->ptrsx == NULL) {
r->ptrsx = q;
}else {
ins_ord(r->ptrsx,q);
}
} else {
if(r->ptrdx == NULL) {
r->ptrdx = q;
} else {
ins_ord(r->ptrdx, q);
}
}
}

nodo* ins_bin(nodo *p) {
nodo *q;
q = creazione();

if(p == NULL) {
return q;
} else {
ins_ord(p, q);
}

return p;
}

void visita(nodo *p){
nodo *r;
r = p;
if(r!=NULL)
{
if(r->ptrsx != NULL) { // controllare il padre
visita(r->ptrsx);
}

printf("%i", r->dato);
printf("\t");

if(r->ptrdx != NULL) {
visita(r->ptrdx);
}
}
}

bool eliminazione(nodo **p, int val)
{
if((*p) == NULL)
return false;
else {
elimina(p);
return true;
}
}

int elimina(nodo **p)
{
int num, risultato;
if((*p)!=NULL)
{
if((*p)->ptrsx == NULL)
{
num = (*p)->dato;
free(*p);
*p=NULL;
risultato=num;
}
else
{
risultato = elimina(&((*p)->ptrdx));
}
}
return risultato;
}


int main()
{
nodo *radice = NULL;
int scelta = 1, num;
while(scelta != 0) {
printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
scanf("%i", &scelta);

switch(scelta) {
case 1: {
radice=ins_bin(radice);

break;
}
case 2: {
printf("\nAlbero:\n");
visita(radice);
printf("\n\n");

break;
}
case 3: {
if(radice != NULL){
printf("\nInserisci il numero da cancellare:\t");
scanf("%d", &num);
radice->ptrsx=NULL;
radice->ptrdx=NULL;
eliminazione(&radice, num);
} else {
printf("\nLa lista e' vuota.\n");
}

break;
}
}
}
}

Grazie mille a tutti :)

[Saetta93]

Con un amico sono arrivato a questo codice:


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
int dato;
struct nodo *ptrsx;
struct nodo *ptrdx;
}nodo;

nodo* creazione(){
nodo *q;
q = malloc(sizeof(nodo));

printf("\nInserisci un numero intero:\t");
scanf("%i", &q->dato);
printf("\n");

q->ptrsx = NULL;
q->ptrdx = NULL;

return q;
}

void ins_ord(nodo *p,nodo *q)
{
nodo *r;
r = p;
if(r->dato > q->dato) {
if(r->ptrsx == NULL) {
r->ptrsx = q;
}else {
ins_ord(r->ptrsx,q);
}
} else {
if(r->ptrdx == NULL) {
r->ptrdx = q;
} else {
ins_ord(r->ptrdx, q);
}
}
}

nodo* ins_bin(nodo *p) {
nodo *q;
q = creazione();

if(p == NULL) {
return q;
} else {
ins_ord(p, q);
}

return p;
}



void visita(nodo *p){
if(p != NULL){
visita(p->ptrsx);
printf("%i\t", p->dato);
visita(p->ptrdx);
}
}

bool eliminazione(nodo *p,int val){
nodo *rd,*rs;
if(p==NULL) return false;
if(p->dato==val){
rs=p->ptrsx;
rd=p->ptrdx;
free(p);
if(rd == NULL)p=rs;
else{
while(rd->ptrsx != NULL) rd=rd->ptrsx;
rd->ptrsx=rs;
p=rd;
}
return true;
}else if (val > p->dato) return eliminazione(p->ptrdx,val);
else return eliminazione(p->ptrsx,val);
}

//funzione per la dellocazione finale dell'albero, usata alla fine del main
void dealloca(nodo *p){
if(p!=NULL){
dealloca(p->ptrsx);
dealloca(p->ptrdx);
free(p);
p=NULL;
}
}

int main()
{
nodo *radice = NULL;
int scelta = 1, num;
while(scelta != 0) {
printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
scanf("%i", &scelta);

switch(scelta) {
case 1: {
radice=ins_bin(radice);

break;
}
case 2: {
printf("\nAlbero:\n");
visita(radice);
printf("\n\n");

break;
}
case 3: {
if(radice != NULL){
printf("\nInserisci il numero da cancellare:\t");
scanf("%d", &num);
radice->ptrsx=NULL;
radice->ptrdx=NULL;
eliminazione(radice, num);
} else {
printf("\nLa lista e' vuota.\n");
}

break;
}
}
}
}


Però qualsiasi numero io voglia cancellare (sia che esista, e sia che non esista), mi elimina sempre la radice, ovvero il primo valore che inserisco nell'albero..

Come mai? :confused:

[Varilion]

perchè setti

radice->ptrsx=NULL;
radice->ptrdx=NULL;

prima di chiamare "eliminazione(radice,val)" ?