Recursividad Arbol Binario y ABB

[Beginner Web]

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 (cpp) [Seleccionar] Expandir


typedef struct tarbol *arbol;
typedef struct tarbol{
char dato;
arbol izq;
arbol der;
};

if(a!=NULL){
  m=a->dato;
  maximo(a,m);
  cout<<"Maximo: "<<m<<endl;
}
  else
cout<<"Arbol vacio"<<endl;

void maximo(arbol a, char &m)
{
  if(a!=NULL){
if(a->dato>m)
m=a->dato;
maximo(a->izq,m);
maximo(a->der,m);
}
}

Y con funcion lo hice asi:

Código (cpp) [Seleccionar] Expandir

//Tengo algo de dudas en esta función porque en bst funciona pero no probe en bt
char maximo(pnodo a)
{
   if(a==NULL)
return '@';
   char letra=a->dato;
   char izquierda=maximo(a->izq);
   char derecha=maximo(a->der);
   if(izquierda>letra)
     letra=izquierda;
   if(derecha>letra)
     letra=derecha;
   return letra;
}

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 (cpp) [Seleccionar] Expandir


char maximo(arbol a)
{
if(a!=NULL){
if(a->der==NULL)
return a->dato;
else
return maximo(a->der);
}
}


[CalgaryCorpus]

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.

[Beginner Web]

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 (cpp) [Seleccionar] Expandir


case 9999: if(arbol==NULL)
cout<<"Arbol vacio"<<endl;
else
cout<<"Maximo: "<<maximo(a)<<endl;
break;
Y el algoritmo recursivo asi:

Código (cpp) [Seleccionar] Expandir

char maximo(pnodo a)
{
if(a->der==NULL)
return a->dato;
else
return maximo(a->der);
}
Pero voy a desistir y me voy a quedar con esto

Código (cpp) [Seleccionar] Expandir

char maximo(pnodo a)
{
if(a==NULL)
return '@';
else{
if(a->der==NULL)
return a->dato;
else
return maximo(a->der);
}
}