[C] Alberi binari maledetti

[Ancosen]

Dunque ecco qua un albero binario (struttura odiosa davvero) vi pongo subito il problema e vi posto il codice che ho elaborato io, la funzione Preorder che dovrebbe sostituire alla radice la somma dei sottoalberi è sbagliata... Cmq ecco il testo completo...

"Progettare un programma C che
legge da stdin un albero binario in preordine e stampa
in preordine su sdtout l'albero ottenuto sostituendo
l'etichetta di ogni nodo r con la somma delle etichette
del sottoalbero con radice r."

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

struct treenode
{
struct treenode *leftptr;
int data;
struct treenode *rightptr;
};
typedef struct treenode TreeNode;
typedef TreeNode *TreeNodeptr;

TreeNodeptr insertnormal();
int PreOrder(TreeNodeptr treeptr);

int main()
{
TreeNodeptr Tree = NULL;
Tree = insertnormal();
PreOrder(Tree);
}

TreeNodeptr insertnormal()
{
int f,value;
TreeNodeptr newPtr = NULL;
scanf("%d %d", &f, &value);
newPtr = (TreeNode*) malloc(sizeof(TreeNode));
if ((newPtr)== NULL)
{
return;
}
else
{
newPtr->data = value;
switch(f)
{
case 0:
newPtr->leftptr = NULL;
newPtr->rightptr = NULL;
break;

case 1:
newPtr->leftptr = insertnormal();
newPtr->rightptr = NULL;
break;

case 2:
newPtr->leftptr = insertnormal();
newPtr->rightptr = insertnormal();
break;
}
return(newPtr);
}
}
int PreOrder(TreeNodeptr treeptr)
{
TreeNodeptr left = NULL;
TreeNodeptr right = NULL;
right = treeptr->rightptr;
left = treeptr->leftptr;
int i = 0;
if(treeptr != NULL)
{
while(left != NULL && right != NULL)
{
i = PreOrder(left) + PreOrder(right);
treeptr-> data = i;
printf("%d", treeptr->data);
}
}
}
Esempio 1.

stdin:
2 0
1 7
0 11
2 9
0 13
0 22

stdout:
2 62
1 18
0 11
2 44
0 13
0 22

Grazie a chiunque mi aiuterà anche con una piccola indicazione. Secondo me è sbagliata la ricorsione però non lo so.. Non lanciate la funzione PreOrder che altrimenti vi da un loop infinito!

[71104]

BWUAHWUHWUAHWA Andrea Cosentino se la sta facendo sotto per l'esame di Programmazione 1 del 28 Feb all'università La Sapienza di Roma!!! :D :D :D
dai scherzo, in bocca al lupo! ;)

[anx721]

io non ho capito com'è rappresentato l'albero in input..qual è il figlio sinistro e quello destro di un nodo?

[71104]

l'albero è da leggere in preordine, quindi il formato è come segue:


<etichetta figlio sinistro (se esiste)>
<esistenza del figlio sx> <esistenza del figlio dx> <etichetta padre>
<etichetta figlio destro (se esiste)>


per esempio, se un albero è etichettato con la scritta "ciao" e i suoi due figli sono rispettivamente "come" e "stai", la sua rappresentazione in preordine è la seguente:


come
1 1 ciao
stai


dove i due 1 sono dei flag che indicano l'esistenza dei figli.

[71104]

non vorrei però essermi confuso con l'inorder; in tal caso il formato del preorder sarebbe:


<esistenza del figlio sx> <esistenza del figlio dx> <etichetta padre>
<etichetta figlio sinistro (se esiste)>
<etichetta figlio destro (se esiste)>


esempio:


1 1 ciao
come
stai

[Ancosen]

Ma ci conosciamo io e te? Almeno di nome? oppure di vista?

[anx721]

io ancora non ho capito com'è rappresentato st'albero in input

[71104]

Originariamente inviato da Ancosen
Ma ci conosciamo io e te? Almeno di nome? oppure di vista?
non te lo dico :p
come sono dispettoso :D

[Ancosen]

e dai... Stiamo andando un po' OT mi pare...:D :D

[71104]

ok, fine dell'OT, sono uno dell'università del 1° anno; ti do un indizio: su TWiki sono famoso... :D :D
ora torniamo IT ;)

[Ancosen]

Ah forse ho capito... Sei quel ragazzo a cui avrebbero dovuto testare l'ultimo homework anche con i negativi? :D

[Ancosen]

Tornando IT l'albero è letto in PreOrder, quindi faccio lo switch dei figli e creo i nodi a seconda del numero dei figli.. Il problema è la seconda parte... Mi sono allenato parecchio e ho fatto un sacco di problemi di vecchi esami del Prof...

[anx721]

Se il problema è la seconda parte, cioè aggiornare l'etichetta di un nodo con la somma delle etichette del sottoalbero corrispondente basta fare cosi:


int aggiorna(TreeNodeptr tree){
if(tree == NULL)
return 0;
//sommo all'etichetta della radice le etichette del
//sottoalbero sinistro
tree -> data += aggiorna(tree -> leftptr);
//sommo all'etichetta della radice le etichette del
//sottoalbero destro
tree -> data += aggiorna(tree -> rightptr);
return tree -> data;
}



aggiorna esegue una visita inorder dell'albero tree; dopo la visita ogni nodo r dell'albero avrà per etichetta la somma delle etichette del sottoalbero radicato in r. aggiorna ritorna l'etichetta aggiornata del nodo radice.

Dopo aver usato la funzione aggiorna, ti basta fare una visita in preorder dell'albero per stamparlo

[71104]

Originariamente inviato da Ancosen
Ah forse ho capito... Sei quel ragazzo a cui avrebbero dovuto testare l'ultimo homework anche con i negativi? :D
indovinato! :D
piace anche a me cazzeggiare su HwUpgrade :D
e poi di tanto in tanto si trova anche qualcosa di utile ;)

[/\/\@®¢Ø]

Originariamente inviato da Ancosen
Dunque ecco qua un albero binario (struttura odiosa davvero) vi pongo subito il problema e vi posto il codice che ho elaborato io, la funzione Preorder che dovrebbe sostituire alla radice la somma dei sottoalberi è sbagliata... Cmq ecco il testo completo...

"Progettare un programma C che
legge da stdin un albero binario in preordine e stampa
in preordine su sdtout l'albero ottenuto sostituendo
l'etichetta di ogni nodo r con la somma delle etichette
del sottoalbero con radice r."

Se guardi bene non ti e' mai chiesto di costruire l'albero, ma solo di leggerlo in preordine e scriverlo in preordine.
Per ogni nodo tu hai bisogno solo del nuovo valore dei figli (oltre che del valore del nodo stesso), e il risultato serve solo al padre.
Tralasciando la stampa del risultato, questo vuol dire che la funzione chiesta dall'esercizio non e' altro che la seguente (codice stile python per brevita'):


def tree():
"""Leggi il prossimo nodo dalla linea di comando, procedi con
eventuali figli e ritorna la somma totale"""
sons,value = leggi_la_prossima_linea()
for n in range(0,sons):
value = value + tree()
return value


E per la stampa del risultato ?
Se fosse richiesto in ordine postfisso, sarebbe molto semplice, basterebbe stampare il risultato non appena calcolato prima di ritornarlo:


def tree():
"""Leggi il prossimo nodo dalla linea di comando, procedi con
eventuali figli e ritorna la somma totale"""
sons,value = leggi_la_prossima_linea()
for n in range(0,sons):
value = value + tree()
print sons,value
return value


In questo pero' modo la radice verrebbe stampata per ultima e non per prima. A noi serve il contrario, per cui invece che stamparla direttamente, la memorizziamo in una struttura dati (che sara' pero' piu' semplice di un albero binario ;) ), e alla fine stampiamo i valori trovati in ordine inverso.
Anche convertito in C, non dovresti andare oltre alle 25-30 linee di codice.

[Ancosen]

Originariamente inviato da 71104
indovinato! :D
piace anche a me cazzeggiare su HwUpgrade :D
e poi di tanto in tanto si trova anche qualcosa di utile ;)

Si, in effetti è divertente! E poi c'è un sacco di gente in gamba, spesso mi aggiorno qua anche sui nuovi dispositivi hardware! A te come è andato lab? che esercizi c'erano? Ho visto che i risultati del 14 non sono ancora usciti...

Grazie a tutti quelli che mi hanno risposto
;)

[71104]

Originariamente inviato da Ancosen
Si, in effetti è divertente! E poi c'è un sacco di gente in gamba, spesso mi aggiorno qua anche sui nuovi dispositivi hardware! A te come è andato lab? che esercizi c'erano? Ho visto che i risultati del 14 non sono ancora usciti...
ehm... veramente siamo ancora OT, cmq laboratorio mi è andata male, c'è stata na storia... il giorno della prova non riuscivo a loggarmi perché il mio account improvvisamente non funzionava +!!! :mad: alla fine si è capito che era un problema di KDE e sono riuscito a loggarmi su Gnome, ma tra una cosa e l'altra ci abbiamo messo 3 quarti d'ora!!! e l'esame era già iniziato e io morale della storia ho avuto solo un'ora di tempo anziché 2 :mad: :muro:
non ci sono parole, è stata una cosa vergognosa; ho anche chiesto al prof se vista la situazione poteva cancellare il mio nome e permettermi di tornare all'appello successivo, ma niente :mad:
morale della storia sono riuscito a svolgere solo 3 esercizi su 9, però forse non è neanche detto che sia andata tanto male perché il migliore che c'era è riuscito a farne 4 e uno sa che è sbagliato :p
forse un 24 riesco ad accaparrarmelo...
cmq ti do una dritta: il tronci dice che all'esame è possibile portarsi dei pezzi di codice fatti a casa; tu fatti TUTTI gli esercizi del 25 e portati quelli, perché i nostri erano estremamente simili ;)
se vogliamo continuare la discussione andiamo su TWiki
ciao :)

[Ancosen]

ok per twiki.

[mpattera]

per fare la somma dei sottoalberi la soluzione più razionale sarebbe un tipo di visita in postorder cmq..