Ciao a tutti
sono un studente d'informatica
devo fare questo progetto
Realizzare lo script tree.sh, con possibile opzione -f, che prende come
input un vettore binario u di lunghezza 2n e controlla che descriva un
albero planare con radice. Precisamente si deve testare che:
1.|u|(1)=|u|(0) (cioè il numero di elementi 1 e 0 in u è lo stesso);
2.per ogni prefisso u' di u, si ha |u'|(1)>|u'|(0).
L'opzione -f calcola anche il numero di foglie dell'albero, nel caso in
cui u rappresenti effettivamente un albero planare.
Dovranno essere effettuati tutti i controlli necessari per evitare
malfunzionamenti del programma.
===============================
Nota per la comprensione del testo:
dato un vettore binario u che soddisfi le proprietà 1. e 2. elencate sopra,
si può associare ad esso in maniera univoca un albero planare con radice
nel modo seguente:
a) al vettore vuoto di lunghezza 0 corrisponde l'albero planare avente
un solo nodo e nessun ramo;
b) se u ha lunghezza 2n>0, percorrendo u da sinistra verso destra, ogni
volta che si incontra un 1 si aggiunge un ramo all'albero, mentre ogni
volta che si incontra uno 0 si risale l'albero lungo il ramo incidente
il nodo in cui ci si trova.
Esempio:
u=(1 1 0 1 0 1 1 0 0 0) corrisponde all'albero
1
/
2
/|\
3 4 5
|
6
in quanto:
1) dal nodo 1 si scende al nodo 2 perchè u(1)=1;
2) dal nodo 2 si scende al nodo 3 perchè u(2)=1;
3) dal nodo 3 si risale al nodo 2 perchè u(3)=0;
4) dal nodo 2 si scende al nodo 4 perchè u(4)=1;
5) dal nodo 4 si risale al nodo 2 perchè u(5)=0;
6) dal nodo 2 si scende al nodo 5 perchè u(6)=1;
7) dal nodo 5 si scende al nodo 6 perchè u(7)=1;
Cool dal nodo 6 si risale al nodo 5 perchè u(Cool=0;
9) dal nodo 5 si risale al nodo 2 perchè u(9)=0;
10) dal nodo 2 si risale al nodo 1 perchè u(10)=0.
In un albero planare con radice, ciascun nodo di grado 1 diverso dalla
radice viene chiamato foglia.
HO AVUTO I PROBLEMI X REALIZZARLO
MI POTETE AIUTARE
VI RINGRAZIO TANTISSIMO
