Esercizio Semplice alberi binari

maghat

il 12 giu 2018, 11:06

7 risposte

maghat

Pochi posts

Iscritto da: giu, 2018

Messaggi:: 4

Esercizio Semplice alberi binari

12 giu 2018, 11:26

Salve a tutti ragazzi, nel prepararmi per l' esame di programmazione sto svolgendo alcuni esercizi.
Ce n'è uno abbastanza semplice che non riesco a risolvere:
IN pratica: Dato un albero binario :


typedef unsigned int Data;
struct BinTreeNode
{
  Data info;
  struct BinTreeNode *left, *right;
};

La funzione singleChildSum () restituisce la somma di tutti i nodi che hanno 1 solo successore
Ecco il mio codice:


#include "es3.h"
#include <stdio.h>
#include <stdlib.h>

int valse1sucessore(BinTree src){//restituisce il valore se il nodo ha 1 successore
    if( src->left==NULL && src->right!=NULL && src->right->right==NULL && src->right->left==NULL){
        	return src->info;}
    if(src->left==NULL && src->right!=NULL && src->right->right==NULL && src->right->left==NULL){
        	return src->info;}
        return 0;
    }


int singleChildSum( BinTree src ){	 //controlla tutti i sottoalberi destri e sinistri, se hanno 1 successore restituisce il valore, 		
							//altrimenti arriva fino al sottoalbero nullo per restituire 0.

	if(src==NULL){
		return 0;}
	return ha1sucessore(src)+singleChildSum(src->left)+singleChildSum(src->right); 
}

Ho provato un sacco di volte, il codice si compila e ma il correttore mi dice che è sbagliato, su 10 test se ne trovano solo 2.

Ringrazio infinitamente chiunque mi aiuti!

7 Risposte

S
smalldragon
Molto attivo
Iscritto da
nov, 2008
Messaggi:
895
Re: Esercizio Semplice alberi binari
12 giu 2018, 13:06
Ciao
scusami ma la funzione di inserimento dell'albero dove stà?
che problema tieni non lo hai indicato quindi presumo che non sia di compilazione.
ti restituisce 0,pur essendoci i dati, o un valore che non capisci?

maghat

Pochi posts

Iscritto da: giu, 2018

Messaggi:: 4

Re: Esercizio Semplice alberi binari

12 giu 2018, 13:48

Ciao, grazie mille per la risposta.
La mia è un esercitazione, quindi io devo solo scrivere la funzione che restituisca la somma dei nodi aventi un solo successore. La funzione di inserimento dell' albero e il resto verranno dichiarati a parte da un correttore che si occuperà di controllare la funzione che ho scritto.
In pratica: scrivi la funzione in un file, poi lanci il correttore che si occupa di assegnargli l' albero di input, verificare che funzioni ecc.
Il mio problema non è di compilazione, il file si compila senza probleme, pero poi lancio il correttore e mi da 8 fallimenti con 10 prove.

Test number 1 out of 10
src Tree
( 17 ( 4 ( 19 ( 1 ( 13 () () ) () ) () ) ( 18 () ( 2 ( 9 () () ) () ) ) ) ( 7 () ( 11 ( 16 () ( 6 () () ) ) ( 10 ( 7 () () ) ( 12 () () ) ) ) ) )
sum = 16
FAILURE
Current success rate: 0.00%

*************************************************

Test number 2 out of 10
src Tree
( 5 () ( 1 () ( 10 ( 2 ( 13 () () ) () ) () ) ) )
sum = 0
FAILURE
Current success rate: 0.00%

*************************************************

Test number 3 out of 10
src Tree
( 2 ( 17 ( 1 ( 7 () () ) () ) ( 14 ( 6 () () ) ( 8 ( 16 () () ) () ) ) ) ( 8 ( 18 ( 16 ( 8 () () ) () ) ( 7 ( 14 () () ) ( 4 () () ) ) ) () ) )
sum = 0
FAILURE
Current success rate: 0.00%

*************************************************

Test number 4 out of 10
src Tree
( 6 () ( 1 () () ) )
sum = 6
SUCCESS
Current success rate: 10.00%

*************************************************

Test number 5 out of 10
src Tree
( 13 ( 17 ( 16 () ( 7 ( 9 () () ) ( 17 () () ) ) ) () ) () )
sum = 0
FAILURE
Current success rate: 10.00%

*************************************************

Test number 6 out of 10
src Tree
()
sum = 0
SUCCESS
Current success rate: 20.00%

*************************************************

Test number 7 out of 10
src Tree
( 15 ( 17 ( 9 ( 15 () ( 1 () () ) ) ( 17 ( 11 () () ) ( 5 () () ) ) ) ( 14 ( 4 ( 4 () () ) () ) ( 8 ( 4 () () ) ( 1 () () ) ) ) ) ( 9 () ( 15 ( 8 () ( 10 () () ) ) ( 11 () () ) ) ) )
sum = 23
FAILURE
Current success rate: 20.00%

*************************************************

Test number 8 out of 10
src Tree
( 10 ( 3 ( 10 ( 3 () () ) () ) ( 8 () ( 18 () ( 0 () () ) ) ) ) ( 16 ( 9 () () ) () ) )
sum = 18
FAILURE
Current success rate: 20.00%

*************************************************

Test number 9 out of 10
src Tree
( 1 () ( 10 ( 11 ( 2 () () ) ( 3 ( 19 () () ) () ) ) ( 7 ( 17 () () ) ( 9 ( 6 () () ) () ) ) ) )
sum = 0
FAILURE
Current success rate: 20.00%

*************************************************

Test number 10 out of 10
src Tree
( 2 ( 16 () ( 5 ( 2 () () ) () ) ) () )
sum = 0
FAILURE
Current success rate: 20.00%

*************************************************

FINAL SUCCESS RATE: 20.00%

Questo è quello che mi restituisce il correttore: quindi funzione solo nel caso : L' albero di partenza sia nullo, oppure abbia un solo successore.

Quindi mi chiedo: nella funzione che ho scritto deve esserci qualche errore logico, del quale però non riesco ad accorgermi.
Grazie mille ancora!

S
smalldragon
Molto attivo
Iscritto da
nov, 2008
Messaggi:
895
Re: Esercizio Semplice alberi binari
12 giu 2018, 15:53
maghat ha scritto:
int valse1sucessore(BinTree src){//restituisce il valore se il nodo ha 1 successore
if( src->left==NULL && src->right!=NULL && src->right->right==NULL && src->right->left==NULL){
return src->info;}
if(src->left==NULL && src->right!=NULL && src->right->right==NULL && src->right->left==NULL){
return src->info;}
return 0;
}
allora in questa funzione tu controlli 4 puntatori quando in realtà ne dovresti coltrollare soltanto due!
xche se i puntatori del nodo corrente sono entrambi a null significa che l'albero in quel nodo e finito.
poi sempre nella stessa funzione tu hai messo un return 0 se le condizioni non si verificano
mentre se le condizioni non si verificano hai i seguenti casi:
1) src->left può essere nullo ma src->right non lo è e in questo caso dovresti sommare il valore e continuare con il nodo valido.
2) src->left non è nullo ma src->right può esserlo e in questo caso dovresti sommare il valore e continuare con il nodo valido.
3) src->left non è nullo cosi come non lo è src->right in questo caso devi andare a verificare i nodi successivi

maghat

Pochi posts

Iscritto da: giu, 2018

Messaggi:: 4

Re: Esercizio Semplice alberi binari

12 giu 2018, 16:54

Ciao, grazie ancora, in quella funziono controllo se un nodo i ha 1 solo successore, ponendo che o destro o sinistro siano null; se questa condizione si verifica, controllo anche che quel successore sia una foglia.
Cosi facendo però devo controllare 4 puntatori: i due del nodo di partenza, e i due dell eventuale foglia. In caso di esito positivo, devo poi prendere il valore della foglia.

ho riscritto la funzione in modo spero più semplice, ma comunque non va


int vha1sucessore(BinTree src){//controlla che il nodo abbia un solo successore
    if(src->right==NULL && src->left!=NULL){ // c' è solo ramo sinistro
        if(src->left->left==NULL && src->left->right==NULL) //controlla che il ramo sinistro non abbia figli
        {return src->info;}} //ritorna il valore del nodo in quanto non ha figli
    if(src->right!=NULL && src->left==NULL) { // controlla che c' è solo il ramo destro
        if (src->right->right==NULL && src->right->left==NULL){//controlla che non abbia figli
            return src->info;}}// ritorna il valore ddel nodo in quanto non ha figli

    return 0;} // se le condizioni non sono rispettate, vuol dire che il nodo non ha 1 solo successore e ritorna 0

Poi chiamando la funzione dovrebbe accadere questo



int singleChildSum( BinTree src )
{if(src==NULL){
return 0;}
if(vha1sucessore(src)==0){
    return singleChildSum(src->left)+singleChildSum(src->right);}// se non ha 1 solo successore richiama le funzioni sui sui alberi destro e sinistro

    return vha1sucessore(src);
    //se trova un nodo che non ha un solo figlio ritorna il valore del nodo
    //altrimenti si vede se la rispettano i suoi sottoalberi, ritonando il valore del nodo quando la condizione è stata rispettato, in modo che i valori dei nodi si sommino


}

DI nuovo grazie 1000

S
smalldragon
Molto attivo
Iscritto da
nov, 2008
Messaggi:
895
Re: Esercizio Semplice alberi binari
12 giu 2018, 17:13
Di nulla e un piacere essere utili
spero che adesso il test vada se ci sono altri problemi postali pure.
M
maghat
Pochi posts
Iscritto da
giu, 2018
Messaggi:
4
Re: Esercizio Semplice alberi binari
12 giu 2018, 20:18
Purtroppo ancora niente, il test da esattamente lo stesso risultato.
Non riesco a spiegarmi il perché!
S
smalldragon
Molto attivo
Iscritto da
nov, 2008
Messaggi:
895
Re: Esercizio Semplice alberi binari
14 giu 2018, 14:22
Ciao
maghat ha scritto:
int vha1sucessore(BinTree src){//controlla che il nodo abbia un solo successore
if(src->right==NULL && src->left!=NULL){ // c' è solo ramo sinistro
if(src->left->left==NULL && src->left->right==NULL) //controlla che il ramo sinistro non abbia figli
{return src->info;}} //ritorna il valore del nodo in quanto non ha figli
if(src->right!=NULL && src->left==NULL) { // controlla che c' è solo il ramo destro
if (src->right->right==NULL && src->right->left==NULL){//controlla che non abbia figli
return src->info;}}// ritorna il valore ddel nodo in quanto non ha figli
return 0;} // se le condizioni non sono rispettate, vuol dire che il nodo non ha 1 solo successore e ritorna 0
allora da quanto hai scritto hai lo stesso problema di prima!
analizziamo bene cosa fa il tuo codice:
```
if(src->right==NULL && src->left!=NULL){ // c' è solo ramo sinistro
        if(src->left->left==NULL && src->left->right==NULL) //controlla che il ramo sinistro non abbia figli
        {return src->info;}} //ritorna il valore del nodo in quanto non ha figli
```
qui verifichi se il nodo letto a un link sinistro
poi vai a vedere se il nodo del link sinistro non ha link validi.
se c'e li ha che cosa fai?
annulli tutto
```
   if(src->right!=NULL && src->left==NULL) { // controlla che c' è solo il ramo destro
        if (src->right->right==NULL && src->right->left==NULL){//controlla che non abbia figli
```
e vai a fare la stessa cosa per il link destro nel quale si verifica lo stesso problema!
termini la routine
quando :
1) il link successivo di un nodo è <> null (non importa se destro o sinistro!)
2) quando entrambi i link del nodo letto sono <> Null
la seconda condizione ci può pure stare ma la prima no! xche cosi non scorri tutto l'albero!
la cosa funziona nel seguente modo:
1) leggi il nodo
2) il nodoletto ha entrambi i link a null?
2.1) si allora termina la routine
3) il nodo letto ha un solo link?
3.1) si varsomma = varsomma+dato del nodo letto o varsomma=varsomma+link
3.2)vai al punto 1 utilizzando il link disponibile.
4)no termina routine facendo restituire un codice che significhi albero troppo complesso.

Devi accedere o registrarti per scrivere nel forum

7 risposte