PDA

Visualizza la versione completa : [c++] Visita in profondità


brumac
03-02-2004, 12:05
Salve a tutti, ho un problema.

Ho definito una struttura dati ad albero binario non bilanciato( cioè non è detto che ogni nodo abbia due figli, ma può averne anche solo uno o zero). Questo albero può avere al massimo 32 livelli. Voglio effettuare una ricerca in profondità, che conti quanti nodi ci sono all'interno dell'albero. Le classi che ho definito sono:

class Nodo {

private:
int link;

public:

Nodo * sx;
Nodo * dx;

Nodo(int l) {
link = l;
sx=0;
dx=0;
}

Nodo() {
link = -1;
sx = 0;
dx = 0;
}

~Nodo() { }

int getLink() { return link; }

void setLink(int l) { link = l; }

};

class Tree {

public:

Nodo *root;

Tree(){

root = new Nodo();
}

~Tree(){}


Ho costruito un albero mediante un metodo build, che qui non ho riportato. Una volta contati i nodi voglio moltiplicare il numero dei nodi per la size di un singolo nodo, in modo da trovare la size di tutto l'albero.

Spero che qualcuno possa aiutarmi.

anx721
03-02-2004, 14:37
Una volta contati i nodi voglio moltiplicare il numero dei nodi per la size di un singolo nodo, in modo da trovare la size di tutto l'albero.

Che intendi per size di un nodo?

Luc@s
03-02-2004, 16:20
penso intenda l'altezza dell'albero o + probabilmente il numero di nodi :D

iguana13
03-02-2004, 16:56
Io l'avrei fatta in questo modo circa:
(uso una struttura ad albero + semplice)


int conta (nodo * radice)
{
// Calcola il nodo corrente
int i = 1;

// Nodo sinistro
if(radice->sx != NULL) {
i = i + conta(radice->sx);
}

// Nodo destro
if(radice->dx != NULL) {
i = i + conta(radice->dx);
}

return i;
}


Ma non funziona... :dhò:
Chi sa dirmi perchè?

Loading