LabASD - Alberi binari di ricerca

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-19

Implementare un albero binario di ricerca (BST, binary search tree) non bilanciato.

Il file bst.h contiene la specifica dell'interfaccia del BST. Si chiede di realizzare le funzioni indicate. È possibile definire ulteriori funzioni che si ritengano necessarie.

Un nodo di un BST è definito dalla struttura:

typedef int BSTKey;
typedef struct BSTNode {
    struct BSTNode *parent, *left, *right;
    BSTKey key;
} BSTNode;

dove BSTKey è il tipo dell'informazione mantenuta in ciascun nodo (di default, un valore intero), mentre parent, left e right sono rispettivamente puntatori al padre, al figlio sinistro e al figlio destro. Nel caso della radice si avrà parent == NULL. Un esempio è mostrato nella Figura 1.

Figura 1: Esempio di albero binario di ricerca
Figura 1: Esempio di albero binario di ricerca

La specifica delle funzioni è indicata nel file bst.h. La funzione bst_pretty_print() (che suggerisco di lasciare per ultima, dato che è la meno importante) stampa un BST in modo un po' più leggibile, ruotando di 90 gradi quanto viene stampato.

Ad esempio, la funzione bst_pretty_print() potrebbe produrre l'output seguente:

   55
12
      9
   5
      -3

che rappresenta l'albero:

         12
        /  \
       5    55
      / \
    -3   9

Il programma bst-main.c legge da standard input una sequenza di comandi, uno per ogni riga, che manipolano un BST inizialmente vuoto. I comandi sono descritti nella tabella seguente, dove k è una chiave intera.

Comando Significato
+ k Inserisci la chiave k
- k Cancella il nodo contenente k, se presente
? k Verifica se la chiave k è presente
s Stampa il numero di nodi (size) nell'albero
h Stampa l'altezza dell'albero
p Stampa il contenuto dell'albero

Un esempio di file di input è bst.in.

Per compilare:

    gcc -std=c90 -Wall -Wpedantic bst.c bst-main.c -o bst-main

Per eseguire:

    ./bst-main < bst.in

oppure

    ./bst-main bst.in

Si assuma che BSTKey sia il tipo int.

Per approfondire

File