Esercizio su alberi binari

In risposta al commento di bkfsec nel post Scritto Settembre 2008.

Mi sembra di capire che mi stai chiedendo di risolvere l’esercizio 2 dell’esame di Algoritmi e Strutture Dati (Unical) del 2 Settembre 2008 (link).

Riporto di seguito quanto chiesto dall’esercizio.

Si scriva una funzione che, dato in input un vettore di caratteri, di dimensione n=2^k con k >0, costruisca un albero binario di stringhe (completo) con le seguenti caratteristiche:

  • ogni foglia ha come contenuto informativo la stringa “c” dove c è un carattere presente nel vettore; l’ordine in cui sono presenti i caratteri nelle foglie dell’albero è lo stesso in cui essi compaiono nel vettore (cioè la prima foglia a partire da sinistra ha come contenuto il carattere in prima posizione, la seconda foglia il carattere in seconda posizione e così via…);
  • il contenuto informativo dei nodi ad un generico livello i (diverso dal primo) è ottenuto concatenando le stringhe presenti nei suoi due nodi figli;
  • la radice contiene esattamente la stringa costituita dalla concatenazione di tutti i caratteri presenti nel vettore di input. Si ricorda che la funzione di concatenazione di stringhe è strcat(s1,s2,s_out).

Visto che al corso di Algoritmi e Strutture Dati avrete sicuramente utilizzato la classe string (o qualcosa di analogo), possiamo tranquillamente ignorare l’ultimo suggerimento (sulla funzione strcat) e utilizzare la classe string.

Durante il corso avete visto la classe AlberoB (link), che fa proprio al caso nostro.

Che cosa dobbiamo fare per costruire un albero come quello richiesto? Dovremo semplicemente mettere nella radice l’intera stringa e quindi ripetere ricorsivamente l’operazione a sinistra e destra con la prima e la seconda metà della stringa, rispettivamente. Traducendo in codice avremo la seguente funzione.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
AlberoB<string>
costruisciAlbero(
        const string & str)
{
    AlberoB<string> albero(str);
 
    if(str.length() > 1)
    {
        AlberoB<string> a_sin = costruisciAlbero(str.substr(0, str.length()/2));
        albero.insFiglio(SIN, a_sin);
 
        AlberoB<string> a_des = costruisciAlbero(str.substr(str.length()/2,
            str.length()/2));
        albero.insFiglio(DES, a_des);
    }
 
    return albero;
}

Di seguito il codice completo per la stampa dell’albero associato alla parola studiare.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <string>
 
#include "AlberoB.cpp"
 
using namespace std;
 
AlberoB<string> costruisciAlbero(const string & str);
 
template<class T>
void stampaVisitaProfondita(const AlberoB<t> & albero);
 
int main()
{
    const string str = "studiare"; // size = 8 = 2^3
 
    AlberoB<string> albero = costruisciAlbero(str);
    stampaVisitaProfondita(albero);
 
    return 0;
}
 
AlberoB<string>
costruisciAlbero(
        const string & str)
{
    AlberoB<string> albero(str);
 
    if(str.length() > 1)
    {
        AlberoB<string> a_sin = costruisciAlbero(str.substr(0, str.length()/2));
        albero.insFiglio(SIN, a_sin);
 
        AlberoB<string> a_des = costruisciAlbero(str.substr(str.length()/2, str.length()/2));
        albero.insFiglio(DES, a_des);
    }
 
    return albero;
}
 
template<class T>
void
stampaVisitaProfondita(
        const AlberoB<t> & albero)
{
    if(albero.nullo())
        return;
 
    cout << albero.radice() << " ";
 
    if(! albero.foglia())
    {
        stampaVisitaProfondita(albero.figlio(SIN));
        cout << "-1 ";
 
        stampaVisitaProfondita(albero.figlio(DES));
        cout << "-1 ";
    }
}

Ecco l’albero (-1 indica la salita di livello).

studiare stud st s -1 t -1 -1 ud u -1 d -1 -1 -1 iare ia i -1 a -1 -1 re r -1 e -1 -1 -1 -1

3 thoughts on “Esercizio su alberi binari”

  1. Vero si tratta della traccia di settembre di ASD.
    Io cercavo di risolverla un pò diversamente, mettendo i caratteri del vettore nelle foglie, poi concatenando i valori nel nodo padre fino alla radice, come sembra suggerire la traccia, ma la tua soluzione è decisamente più logica, anche se usi la libreria string ;-).

Leave a Reply

Your email address will not be published. Required fields are marked *