Esercitazioni su alberi

Esercitazioni su alberi
Si vuole creare un albero binario di ricerca (BST) contenente interi in
modo da poter eseguire funzioni su esso.
Si astragga il concetto di albero in modo da rendere l’implementazione il
più strutturata possibile.
Esercitazioni su alberi
Per fare ciò si cominci a implementare:
1.Una libreria (element.h, element.c) contenente la definizione dei
tipi di dato e delle funzioni primitive
//DEFINIZIONI
typedef int element;
typedef enum { false, true } boolean;
//DICHIARAZIONI
boolean isLess(element, element);
boolean isEqual(element, element);
element getElement(void);
void printElement(element);
boolean isNull(element);
Esercitazioni sulle alberi
Dove
boolean isLess(element, element);
Controlla se un elemento è minore dell’altro
boolean isEqual(element, element);
Uguaglianza fra elementi
element getElement(void);
Input da tastiera di un elemento
void printElement(element);
Stampa a video di un elemento
void isNull(element);
Controlla che l'elemento sia diverso da 0
Esercitazioni su alberi
Il programma deve prendere in input i numeri da inserire all'interno dell'albero.
Visualizzare un menu nel quale è possibile:
'r' → Generare un nuvo albero,
'<' → Eseguire stampa preorder,
'>' → Eseguire stampa postorder,
'i' → Eseguire stampa inorder,
'/' → Ricerca di un elemento,
'h' → Calcolare l'altezza dell'albero,
's' → Calcolare la somma degli elementi dell'albero,
'n' → Calcolare il numero di nodi,
'b' → Calcolare il bilanciamento dell'albero,
'e' → Uscire dal programma.
Esercitazioni su alberi
Le funzioni di manipolazione delle liste, da inserire nel file tree.c, tree.h
secondo le modalità solite, richieste sono state già introdotte a lezione, di
seguito un rapido ripasso:
typedef struct nodo
{
element value;
struct nodo *left, *right;
} NODO;
typedef NODO *tree;
/*PRIMITIVE*/
boolean empty(tree);
tree emptytree(void);
element root(tree);
tree left(tree);
tree right(tree);
tree cons_tree(element,tree ,tree);
Esercitazioni su alberi
Utilizzando questa base andiamo a implementare le seguenti funzioni.
tree ord_ins(element, tree)
void preorder(tree);
void inorder(tree);
void postorder(tree);
boolean member(element, tree);
int nnodes(tree);
int sum(tree);
int height(tree t);
int height_aux(tree t);
int balance (tree t);

Download Report