Info:

twitter

Ultimi commenti: Comment feed

Tags:

Sponsor:

Archivio 2018:

Giu Mag Feb Gen

Archivio 2017:

Dic Nov Ott Mag Apr Mar Feb Gen

Archivio 2016:

Dic Nov Ott Ago Mag Mar Feb Gen

Archivio 2015:

Nov Ott Set Mar Gen

Archivio 2014:

Dic Nov Ott Set Lug Giu Mag Apr Gen

Archivio 2013:

Dic Nov Set Ago Lug Giu Mag Apr Feb Gen

Archivio 2012:

Dic Nov Ott Set Ago Giu Mag Apr Mar Feb Gen

Archivio 2011:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2010:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2009:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2008:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2007:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

Archivio 2006:

Dic Nov Ott Set Ago Lug Giu Mag Apr Mar Feb Gen

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:
Commenti (6):
1. wac
lunedì 29 novembre 2010 alle 8:48 PM - firefox 3.6.12 Windows 7
   

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.

 

 

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

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

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

Compiti dell'algoritmo

  1. Allocare tutti i nodi
  2. Settare il nodo padre in maniera appropriate per ciascun nodo
  3. 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;

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

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)]; 

}

   
5. wac
lunedì 29 novembre 2010 alle 11:04 PM - firefox 3.6.12 Windows 7
   
   
6. Paperino
martedì 30 novembre 2010 alle 12:51 AM - chrome 7.0.517.44 Windows 7
   

Buone entrambe.

   
Lascia un commento:
Commento: (clicca su questo link per gli smiley supportati; regole di ingaggio per i commenti)
(opzionale, per il Gravatar)