Recursion en bst

[Beginner Web]

Hola, se puede sumar los valores de las ramas interiores de un arbol binario de busqueda? Quiero decir que sume todos los nodos excepo la raiz y las hojas, me parece que con recursividad no se puede pero si alguien sabe como hacerlo me lo hace saber, esto tengo hecho, me suma la raiz y no quiero eso  

Código (cpp) [Seleccionar] Expandir

int sumar(pnodo a)
{
int suma=0;
if(a!=NULL){
suma=sumar(a->izq)+sumar(a->der);
if(a->izq!=NULL || a->der!=NULL)
suma+=a->dato;
}
return suma;
}
Y la funcion iterativa que use para hacer esta operación la hice de esta forma

Código (cpp) [Seleccionar] Expandir

int sumar(pnodo a)
{
tpila p;
int suma=0;
pnodo extraido;
if(a!=NULL){
init_stack(p);
push_stack(p,a);
extraido=pop_stack(p);
if(extraido->izq!=NULL)
push_stack(p,extraido->izq);
if(extraido->der!=NULL)
push_stack(p,extraido->der);
while(!empty_stack(p)){
extraido=pop_stack(p);
if(extraido->izq!=NULL || extraido->der!=NULL)
suma+=extraido->dato;
if(extraido->izq!=NULL)
push_stack(p,extraido->izq);
if(extraido->der!=NULL)
push_stack(p,extraido->der);
}
}
return suma;
}

[CalgaryCorpus]

Se puede hacer recursivamente, en esa función, llamemosla f, suma 0 cuando sea una hoja, suma todo el resto recursivamente, retorna el valor de la suma y haz una función que llame a f y le reste el valor que está en la raíz.

[dijsktra]

Puedes marcar la raiz en el cálculo pasándola por parámetro.

Código (cpp) [Seleccionar] Expandir

int sumar(const pnodo a, const pnodo root)
{
 int suma=0;
 if(a!=NULL){
   suma=sumar(a->izq,root)+sumar(a->der,root);
   if ((a->izq!=NULL || a->der!=NULL) && a!=root) // neither leaf nor root
     suma+=a->dato;
 }
 return suma;
}

// Initial call
pnode a ;
// populate tree a with subtrees
sumar(a,a);


[Beginner Web]

Tiene razón, me siento estupida, pero de todas formas no quiero pasar dos parametros solo el arbol  nada mas y si no se puede pues ni modo. 

[MAFUS]

Puedes llamar a una función (que te haga de interface recibiendo sólo el árbol) y esta llame a la función que hará realmente el trabajo, la de dos argumentos.

Por cierto, deberías empezar a usar clases, trabajas con C++ y te aferras demasiado con el modo C de hacer las cosas.

[Beginner Web]

MAFUS que acabo de escribir arriba? Tiene que ser una sola funcion y recibir un solo parametro y que esa funcion haga todo sino no tiene sentido, si es asi como dices entonces hago un procedimiento y listo pero no. Igual perdonen por no poner arriba esas condiciones me despido con un fuerte abrazo

[dijsktra]

Tiene razón, me siento estupida, pero de todas formas no quiero pasar dos parametros solo el arbol  nada mas y si no se puede pues ni modo.  

Ya... Te entiendo. Para lograrlo, tienes que hacer distinguible la raiz del resto de nodos de algún modo. Y esto se hace de dos maneras:

• O planteas tu structura con un campo "padre", que apunte al nodo padre, en el caso de la raiz null (Recomendable)
• Usas un viejo truco de C, el cualificador "static", que como efecto lateral irá grabado siempre el nivel de descenso

De otro modo no se puede... Es como si, en tu solución iterativa, dijeras que no puedes porque antes del buble while solo está permitido empezar con pilas vacías. O en otra brillante metáfora, dicha por un político en otro contexto

como un hombre con los pies en un cubo tratando de levantase tirando de la asa

Espero que esto te valga   . Ahh! Y no me parece que seas "estúpida" por preguntar eso. La mayoría de los chicos y chicas de tu edad, a los 14 años,  se dedican a jugar a video juegos, sin profundizar en las cuestiones fundamentales de la computación.

Te propongo esta con el "truco" de static

Código (c) [Seleccionar] Expandir



#include <stdlib.h>
#include <stdio.h>

/*    Binary search tree

                       10
      /  \
     5   14
    /  / \
   3   13  15

  Adding non-leaf and non-root nodes, i.e. 19

  Warning: This solution may be not portable to other languages than C
*/

typedef struct nodo {
 struct nodo *izq;
 struct nodo *der;
 int dato;
}  *pnodo;

int sumar(const pnodo a)
{
 static int level = 0 ; // <== An eye to static qualifier (side effect!)
 int suma=0;

 if(a!=NULL){
   level++;  // <=== An eye.
   suma=sumar(a->izq)+sumar(a->der);
   level--; // <== An eye.
   if ((a->izq!=NULL || a->der!=NULL) && level)  //  <=== An eye
suma+=a->dato;
 }
 return suma;
}



int main(int argc, char *args[])
{
 pnodo a=NULL;

/* Raw building of tree. More abstraction might be needed here */
 if ((a = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->dato = 10;
 if ((a->izq = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->izq->dato = 5;
 if ((a->izq->izq = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->izq->izq->dato = 3;  
 if ((a->der = (pnodo )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->der->dato = 14;
 if ((a->der->der = (pnodo )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->der->der->dato = 15;
 if ((a->der->izq = (pnodo )malloc(sizeof(struct nodo)))==NULL)
   {
     perror("malloc");
     exit(1);
   }
 a->der->izq->dato = 13;

 printf("Adding internal nodes %d\n",sumar(a));

}



Esta es la salida del programa

Código [Seleccionar] Expandir


Adding internal nodes 19