visita albero n-ario in C

**streuso83** · 30-05-2009, 14:10

ciao a tutti, vi espongo il mio problema. Ho un albero n-ario in cui ogni nodo e della seguente forma:

struct nodo {
int inf;
struct nodo *figlio;
struct nodo *fratello;
};

Ora avrei bisogno di una funzione che mi visiti l'albero in modo tale come output abbia ogni nodo con tutti i suoi figli.
Non sò se è preordine postordine o altro.
Grazie

**oregon** · 30-05-2009, 14:36

http://it.wikipedia.org/wiki/Albero_(informatica)

**streuso83** · 30-05-2009, 16:01

grazie ma non parla di albero n-ario...solo maledettissimi alberi binari

**Brendon77** · 30-05-2009, 19:05

Ciao provo a darti una mano.

Non ricordo bene il C

, per cui ti posto una sorta di pseudocodice per il Preordine:

codice:

void treePreorder(root) {
   if(root == null) return;

   <visita root>
   r = root.firstChild;  
    while(r != null) {
     treePreorder(r);
     r = r.nextSibling;
   }
}

Naturalmente r è di tipo Nodo .
Non dovresti avere problemi a tradurla in C.
Come vedi è una funzione ricorsiva, la logica non è difficile. Ti consiglio di disegnarti la stuttura dati per avere un'idea più chiara del funzionamento.

Per le altre due visite (InOrder e PostOrder).. la logica è la stessa.... e possono essere un buon esercizio per capire meglio la struttura.

Spero di esserti stato di aiuto

Ciao

**mondobimbi** · 30-05-2009, 23:27

XML lo puoi rappresentare come un albero n-ario.
Mi sono ricordato di aver scritto una funzione per la stampa di un file XML.
Sibling sono i nodi fratelli e child i figli

codice:

string XMLNode::printXML ( const XMLNode * curEl, unsigned int tab ) const
{

	string loc_print = "";
	string p_tab = "";

	if ( curEl ) {

		TYPE type = curEl->type () ;

		switch ( type ) {
			case ELEMENT : {

					XMLElement * el = ( XMLElement *) curEl;
					string tagName = curEl->value ();

					loc_print += p_tab + "<" + tagName ;

					for ( XMLAttribute * att = el->getAttributes() ; att; att = att->next ) {
						string name = att->name ();
						string value = att->value ();
						if ( value != "" )
							loc_print += " " + name + "=\"" + value + "\"";
					}

					if ( curEl->hasChilds() ) {
						loc_print += ">\n";

						if ( tab )
							loc_print += printXML ( curEl->fChild, tab + 1 );
						else
							loc_print += printXML ( curEl->fChild, tab );

							// chiude il tag
						if ( tagName != "" ) {
							loc_print += p_tab + "</" + tagName + ">\n";
						}

					}
					else {
						if ( tagName == "br" || tagName == "img" || tagName == "link" )
							loc_print += " />\n";
						else
							loc_print += "></" + tagName + ">\n";
					}

				}

				break;
			case TEXT :
				loc_print = p_tab + curEl->value () + "\n";
				break;
			case  DOCUMENT :
				if ( curEl->hasChilds() )
					loc_print += printXML ( curEl->fChild, tab );
				break;
			case  COMMENT :
				loc_print = p_tab + "<-- " + curEl->value () + "-->\n";
				break;
			case  UNKNOWN :
				break;
			case  DECLARATION :
				break;
			case  DOCTYPE :
				loc_print = "<!DOCTYPE " + curEl->value () + ">\n";
				break;
			case  SCRIPT :
				loc_print = p_tab + "<? " + curEl->value () + "?>\n";
				break;
			default :
				break;
		}

		if ( curEl->fSibling )
			loc_print += printXML ( curEl->fSibling, tab );

	}

	return loc_print;

}

tab può essere utile per conoscere la profondità.
type è il tipo di nodo e value il suo valore (che tipende dal suo tipo).

Te la passo in modo che dai una occhiata alla sua logica.

ciao
sergio

**streuso83** · 01-06-2009, 11:20

sinceramente ci ho capito poco...

cavolo proprio sto impazzento...

**Brendon77** · 01-06-2009, 12:10

Ciao ri-provo a darti una mano

La struttura dati albero è definita da un nodo radice e da un numero arbitrario 'n' di figli.
I comuni alberi binari di ricerca sono un caso particolari di alberi n-ari.

Un albero n-ario si può rappresentare tramite una lista collegata

Tra le operazioni comuni di un albero, troviamo i diversi tipi di visite.

Quella che ti ho suggerito è la visita preordine.

In pratica dato un nodo v :

1. visita v
2. visita i sotto-alberi aventi come radice i figli di v , da sinistra verso destra

codice:

void treePreorder(root) {
   if(root == null) return;

   <visita root>
   r = root.firstChild;  
    while(r != null) {
     treePreorder(r);
     r = r.nextSibling;
   }
}

con FirstChild il figlio e NextSibling come il fratello successivo.

Ricorda che:
1. Un albero vuoto è sempre un albero.
2. esiste un albero con un solo nodo (radice)
3. Ogni nodo interno dell'albero è esso stesso un sotto-albero

La procedura ricorsiva prende come parametro il nodo da visitare (nel primo caso la radice dell'albero).

Se si è arrivati ad un albero vuoto non si fa nulla, altrimenti visita il nodo in questione (per esempio stampa a video l' informazione in esso contenuta).

Successivamente si passa al figlio (se esiste).. e si richiama ricorsivamente la procedura (prima iterazione del ciclo while ).
Si va quindi in profondità fino ad arrivare alla fine dell'albero (in quel caso r sarà NULL).

In questo caso per effetto della ricorsione, si torna la nodo visitato precedentemente e si eseguono ulteriori iterazioni del ciclo While per visitare tutti i fratelli, ma per ogni fratello (esso stesso un albero) bisogna effettuare di nuovo la visita (così come hai fatto per ogni figlio).

Quindi per ogni iterazione del ciclo si esegue ricorsivamente una visita di ogni albero.
La prima iterazione per il primo figlio... le successive per i fratelli.

Devi cercare di capire bene la struttura e la logica della ricorsione.

Spero di averti aiutato

Ciao

**sebaldar** · 01-06-2009, 12:21

la soluzione che ti ho suggerito io è analoga, stampa prima tutti i figli e poi i fratelli.

Ti ho buttato giù un esempio sulla tua falsariga, spero che non ci siano errori

codice:

#include <stdio.h>

struct nodo {

	int inf;
	struct nodo *figlio;
	struct nodo *fratello;

};

void printNodo ( const struct nodo * n )
{

	if ( n ) {

		printf ( "%d\n", n->inf );
		
		if ( n->figlio )
			printNodo ( n->figlio ) ;
		
		if ( n->fratello )
			printNodo ( n->fratello ) ;

	}
	
}

int main () 
{

	printf ( "inizializzo la struttura\n" );
	
	struct nodo *n = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n->inf = 10;

	struct nodo *n1 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n1->inf = 11;
	struct nodo *n2 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n2->inf = 12;
	struct nodo *n3 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n3->inf = 13;
	struct nodo *n4 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n4->inf = 111;
	
	n->figlio = n1;
	n1->fratello = n2;
	n2->fratello = n3;
	n2->figlio = NULL;
	n3->fratello = NULL;
	n1->figlio = n3;
	n3->fratello = n4;
	n3->figlio = NULL;
	n4->fratello = NULL;
	n4->figlio = NULL;

	printNodo(n);

	return (0);

}

**streuso83** · 01-06-2009, 14:26

grazie per l'aiuto che mi state dando. Vi spiego cosa devo fare...
nell'immagine allegata c'è un esempio di albero che ho. in pratica devo ottenere il seguente risultato:
3 3
3 1 1 1
2 2 2
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1
In pratica tutti i cammini radice foglia dove in questo caso le radici sono i fratelli in alto (3,2,1).
Vi prego aiutatemi

**sebaldar** · 01-06-2009, 17:26

non capisco,
non provi a farlo ?
ciao
sergio

Discussione: visita albero n-ario in C

Strumenti discussione

Ricerca discussione

Visualizza

visita albero n-ario in C

Preordine

Ciao

Permessi di invio