Manugal
29-05-2007, 20:04
Ciao a tutti!
Mi sto scervellando nel trovare un algoritmo (anche in pseudo-codice) che data in input una rappresentazione tramite albero binario di un albero m-ario T, ritorni il numero massimo di figli di un nodo di T.
Io avevo pensato una cosa del genere:
Se l'albero è vuoto confronta il valore max con il conteggio corrente del nodo di T e lo assegna a max
Se il sottoalbero sinistro non è vuoto e il sottoalbero destro lo è allora vado a sinistra, aumento il conteggio di 1 e poi ricorsivamente vado a destra nell'albero
Se il sottoalbero sinistro è vuoto e il sottoalbero destro non lo è allora aumento il conteggio di 1 e poi ricorsivamente vado a destra nell'albero
Se entrambe i sottoalberi sono vuoti allora aumento il conteggio di 1 e vado a destra
Se entrambe i sottoalberi sono pieni allora vado prima a destra e poi a sinistra
Il problema è che non capisco come posso tenermi traccia del conteggio dei figli durante le chiamate ricorsive.
Mi sto scervellando nel trovare un algoritmo (anche in pseudo-codice) che data in input una rappresentazione tramite albero binario di un albero m-ario T, ritorni il numero massimo di figli di un nodo di T.
Io avevo pensato una cosa del genere:
Se l'albero è vuoto confronta il valore max con il conteggio corrente del nodo di T e lo assegna a max
Se il sottoalbero sinistro non è vuoto e il sottoalbero destro lo è allora vado a sinistra, aumento il conteggio di 1 e poi ricorsivamente vado a destra nell'albero
Se il sottoalbero sinistro è vuoto e il sottoalbero destro non lo è allora aumento il conteggio di 1 e poi ricorsivamente vado a destra nell'albero
Se entrambe i sottoalberi sono vuoti allora aumento il conteggio di 1 e vado a destra
Se entrambe i sottoalberi sono pieni allora vado prima a destra e poi a sinistra
Il problema è che non capisco come posso tenermi traccia del conteggio dei figli durante le chiamate ricorsive.