SoloCodigo

Programación General => C/C++ => Mensaje iniciado por: Claudisimo en Lunes 5 de Enero de 2009, 06:36

Título: [C++] 3 preguntas sobre arboles.
Publicado por: Claudisimo en Lunes 5 de Enero de 2009, 06:36

Hola, primera vez que posteo en este foro, se ve bastante buena su comunidad. Los felicito, sigan así, y espero poder integrarme.

Ahora, quería hacer 3 preguntas sobre arboles, aquí van:
1) ¿Como determino la rama mas larga (o las mas largas) de un arbol?
2) ¿Es lo mismo para un arbol AVL?
3) ¿Como cuento los elementos de un arbol? Sin variables globales.... es que como es recursiva la función para recorrerlos, nosé como.

Por último si no pueden ayudarme con código agradecería una idea como hacerlo. Muchas gracias :D

Título: Re: [C++] 3 preguntas sobre arboles.
Publicado por: diego.martinez en Lunes 5 de Enero de 2009, 11:20

veamos:

para la primera pregunta, usa una funcion recursiva y como parametro añadele dos punteros a entero. Dentro de la funcion cambias el contenido de los punteros. En uno guardas el nivel en el que estas, y en el otro el nivel maximo al que has llegado.
Ex:

Código: Text

1.  
2. void SizeBranch ( Node * Nod, int * CurrentBranchSize, int * maxSizeBranch)
3. {
4.  
5. //recursividad normal no añadida
6.  
7. //...
8. //...
9.  
10.  
11.  //al avanzar un nivel
12.    *CurrentBranchSize=*CurrentBranch+1;
13.    
14.  
15.   if( *CurrentBranchSize>*maxSizeBranch) *maxSizeBranch=*CurrentBranchSize;
16.  
17. //al hacer return por que no tiene descendencia
18.   *CurrentBranchSize=*CurrentBranch-1; //por que volvemos un nivel.
19.  
20. }
21.  
22.  

segunda pregunta: si, la unica diferencia del avl es en la insercion, pero esto deberia valer para cualquier arbol.

tercera pregunta:
es mas facil que la primera, simplemente pasa 1 integer e incrementalo en cada iteracion.

Código: Text

1.  
2. void TreeSize(Node * n, int * size)
3. {
4. // recursividad normal ...
5.  
6. *size=*size+1; //esto incrementa size 1 vez por nodo
7. }
8.  
9.