A Ovest Di Paperino

Lunedì quiz 8

Input: un numero intero non tanto grande.

Output: un array contenente i nodi foglia di un albero binario inverso completamente bilanciato di profondità pari al valore in input.

Per albero binario inverso intendo un albero in cui ogni nodo ha un puntantore al nodo “padre”.

BinaryTree

È responsabilità dell’algoritmo allocare un numero necessario e sufficiente di nodi (il campo “data” non è necessario da inizializzare).

-quack

Potrebbero interessarti anche:

Pubblicato lunedì 29 novembre 2010 alle 8:11 PM - Archiviato in: Codice.
Condividi su: Facebook, Wikio, Segnalo.

Commenti (6):

1. wac
lunedì 29 novembre 2010 alle 8:48 PM - firefox 3.6.12

papero non ho capito bene, dato il numero k in input dobbiamo costruire l'albero e poi ritornare un array con i nodi foglia, oppure allocare semplicemente un array con il numero corretto di nodi foglia? Nel secondo caso basta allocare e riempire di nodi un array con 2^(k-1) elementi. Nel primo caso invece, dovremmo allocare un array con 2^k-1 elementi, trattando l'array che rappresenta l'albero in modo simile ad un heap e poi restituire un array contenente le foglie.

Permalink - Rispondi al commento

2. Giuseppe
lunedì 29 novembre 2010 alle 9:47 PM - IE 9.0

Quoto quello che ha detto wac... a meno che non ci sta sfuggendo qualcosa...

Permalink - Rispondi al commento

3. Paperino
lunedì 29 novembre 2010 alle 9:53 PM - chrome 7.0.517.44

Compiti dell'algoritmo

Allocare tutti i nodi
Settare il nodo padre in maniera appropriate per ciascun nodo
Restituire un array (lista o altro) che contenga solo i nodi foglia coi quali ovviamente si può navigare fino al nodo radice percorrendo il puntantore "parent":

class Node
{
Node parent;
}

Permalink - Rispondi al commento

4. Giuseppe
lunedì 29 novembre 2010 alle 10:18 PM - IE 9.0

Vediamo se ci "ingarro"...

Node* Tree;
class Node {
public Node Parent;
};

Node* getLeavesOfTree(int N) {
/* Poiché il numero di roba da allocare è 2^N-1
allora N non può essere maggiore di 64 */

if (N>64) return null;

// Numero di elementi da allocare
long int dim = (1 << N) - 1;
// L'albero
Tree = new Node[dim];
// Impostiamo il padre
for (int i = dim - 1; i > 0; i--) {
Tree[i].Parent = Tree[(int)((i-1)/2)];
}
// Dall'elemento centrale in poi sono tutte foglie
return &Tree[1<<(N-1)];

}