elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Curso de javascript por TickTack


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Recursividad Arbol Binario y ABB		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Recursividad Arbol Binario y ABB  (Leído 1,743 veces)
Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Recursividad Arbol Binario y ABB
« en: 5 Enero 2019, 02:28 am »
Hola estaba viendo mi carpeta del cole y me encontre con esto

1) Codifique un algoritmo recursivo que determine el máximo valor del árbol binario de caracteres.

He hecho esto 1 con procedimiento y me quedo asi
Código
  1. typedef struct tarbol *arbol;
  2. typedef struct tarbol{
  3. 	char dato;
  4. 	arbol izq;
  5. 	arbol der;
  6. };
  7.  
  8. if(a!=NULL){
  9.    m=a->dato;
  10.    maximo(a,m);
  11.    cout<<"Maximo: "<<m<<endl;
  12. }
  13.    else
  14. 	cout<<"Arbol vacio"<<endl;
  15.  
  16. void maximo(arbol a, char &m)
  17. {
  18.    if(a!=NULL){
  19. 		if(a->dato>m)
  20. 			m=a->dato;
  21. 		maximo(a->izq,m);
  22. 		maximo(a->der,m);
  23. 	}
  24. }
  25.  
Y con funcion lo hice asi:
Código
  1. //Tengo algo de dudas en esta función porque en bst funciona pero no probe en bt
  2. char maximo(pnodo a)
  3. {
  4.     if(a==NULL)
  5. 	return '@';
  6.     char letra=a->dato; 
  7.     char izquierda=maximo(a->izq); 
  8.     char derecha=maximo(a->der); 
  9.     if(izquierda>letra) 
  10.       letra=izquierda; 
  11.     if(derecha>letra) 
  12.       letra=derecha; 
  13.     return letra;
  14. }

Luego la consigna dice:
2) Modofique el algoritmo del ítem anterior para que la busqueda se realice en un arbol binario de busqueda

Y ese lo hice asi:
Código
  1. char maximo(arbol a)
  2. {
  3. 	if(a!=NULL){
  4. 		if(a->der==NULL)
  5. 			return a->dato;
  6. 		else
  7. 			return maximo(a->der);
  8. 	}
  9. }
  10.  
« Última modificación: 5 Enero 2019, 06:14 am por Beginner Web » En línea
7w7
CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: Recursividad Arbol Binario y ABB
« Respuesta #1 en: 5 Enero 2019, 13:46 pm »
En el caso del ABB todas las veces (o la mayoría) que ingresas a la función haces 2 comparaciones, contra null primero y luego si el de la derecha es null. Dada esta última, no es posible que las llamadas recursivas se encuentren con punteros null.

Puedes ahorrarte la primera comparación. Un truco es tener 2 funciones, una que hace la comparación contra null que no es recursiva y que invoca a otra que si es recursiva, pero que no compara contra null.
En línea
Aqui mi perfil en LinkedIn, invitame un cafe aqui
Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Re: Recursividad Arbol Binario y ABB
« Respuesta #2 en: 5 Enero 2019, 20:31 pm »
Cita de: CalgaryCorpus en  5 Enero 2019, 13:46 pm
En el caso del ABB todas las veces (o la mayoría) que ingresas a la función haces 2 comparaciones, contra null primero y luego si el de la derecha es null. Dada esta última, no es posible que las llamadas recursivas se encuentren con punteros null.

Puedes ahorrarte la primera comparación. Un truco es tener 2 funciones, una que hace la comparación contra null que no es recursiva y que invoca a otra que si es recursiva, pero que no compara contra null.




Ay verdad si cierto!
Entonces me quedaria asi en el main:
Código
  1. case 9999: if(arbol==NULL)
  2. 			cout<<"Arbol vacio"<<endl;
  3. 		else
  4. 			cout<<"Maximo: "<<maximo(a)<<endl;
  5. 		break;
Y el algoritmo recursivo asi:
Código
  1. char maximo(pnodo a)
  2. {
  3. 	if(a->der==NULL)
  4. 		return a->dato;
  5. 	else
  6. 		return maximo(a->der);
  7. }

Pero voy a desistir y me voy a quedar con esto ;)
Código
  1. char maximo(pnodo a)
  2. {
  3. 	if(a==NULL)
  4. 		return '@';
  5. 	else{
  6. 		if(a->der==NULL)
  7. 			return a->dato;
  8. 		else
  9. 			return maximo(a->der);
  10. 		}
  11. }
  12.  
« Última modificación: 6 Enero 2019, 01:47 am por Beginner Web » En línea
7w7
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Altura de arbol binario
Java 		l337* 4 36,766 Último mensaje 5 Diciembre 2009, 13:08 pm
por imnohacker
Arbol binario Ejemplo
.NET (C#, VB.NET, ASP) 		S1dD3xt35 0 7,627 Último mensaje 21 Abril 2010, 07:18 am
por S1dD3xt35
arbol binario
Programación C/C++ 		karmi 2 4,444 Último mensaje 14 Diciembre 2010, 22:08 pm
por ANTÓN RAMIREZ
Ayuda recursividad y árbol java.
Ejercicios 		Caruko 0 2,669 Último mensaje 17 Noviembre 2014, 21:02 pm
por Caruko
Arbol binario
Java 		pabelsbf 2 2,016 Último mensaje 14 Diciembre 2016, 01:20 am
por pabelsbf
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines