Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: Beginner Web en 12 Enero 2019, 01:59 am


Título: Recursion en bst
Publicado por: Beginner Web en 12 Enero 2019, 01:59 am
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  >:D
Código
  1. int sumar(pnodo a)
  2. {
  3. 	int suma=0;
  4. 	if(a!=NULL){
  5. 		suma=sumar(a->izq)+sumar(a->der);
  6. 		if(a->izq!=NULL || a->der!=NULL)
  7. 			suma+=a->dato;
  8. 	}
  9. 	return suma;
  10. }
Y la funcion iterativa que use para hacer esta operación la hice de esta forma
Código
  1. int sumar(pnodo a)
  2. {
  3. 	tpila p;
  4. 	int suma=0;
  5. 	pnodo extraido;
  6. 	if(a!=NULL){
  7. 		init_stack(p);
  8. 		push_stack(p,a);
  9. 		extraido=pop_stack(p);
  10. 		if(extraido->izq!=NULL)
  11. 			push_stack(p,extraido->izq);
  12. 		if(extraido->der!=NULL)
  13. 			push_stack(p,extraido->der);
  14. 		while(!empty_stack(p)){
  15. 			extraido=pop_stack(p);
  16. 			if(extraido->izq!=NULL || extraido->der!=NULL)
  17. 				suma+=extraido->dato;
  18. 			if(extraido->izq!=NULL)
  19. 				push_stack(p,extraido->izq);
  20. 			if(extraido->der!=NULL)
  21. 				push_stack(p,extraido->der);
  22. 		}
  23. 	}
  24. 	return suma;
  25. }

Título: Re: Recursion en bst
Publicado por: CalgaryCorpus en 12 Enero 2019, 04:07 am
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.

Título: Re: Recursion en bst
Publicado por: dijsktra en 17 Enero 2019, 14:35 pm
Puedes marcar la raiz en el cálculo pasándola por parámetro.

Código
  1. int sumar(const pnodo a, const pnodo root)
  2. {
  3.   int suma=0;
  4.   if(a!=NULL){
  5.     suma=sumar(a->izq,root)+sumar(a->der,root);
  6.     if ((a->izq!=NULL || a->der!=NULL) && a!=root) // neither leaf nor root
  7.       suma+=a->dato;
  8.   }
  9.   return suma;
  10. }
  11.  
  12. // Initial call
  13. pnode a ;
  14. // populate tree a with subtrees
  15. sumar(a,a);
  16.  

Título: Re: Recursion en bst
Publicado por: Beginner Web en 18 Enero 2019, 23:37 pm
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.  :-(

Título: Re: Recursion en bst
Publicado por: MAFUS en 19 Enero 2019, 21:01 pm
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.

Título: Re: Recursion en bst
Publicado por: Beginner Web en 19 Enero 2019, 21:09 pm
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

Título: Re: Recursion en bst
Publicado por: dijsktra en 21 Enero 2019, 10:47 am
Cita de: Beginner Web en 18 Enero 2019, 23:37 pm
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

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

Espero que esto te valga  :D . 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
  1.  
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4.  
  5. /*    Binary search tree
  6.  
  7.                         10
  8. 		       /  \
  9. 		      5	   14
  10. 		     / 	  / \
  11. 		    3  	 13  15
  12.  
  13.    Adding non-leaf and non-root nodes, i.e. 19
  14.  
  15.    Warning: This solution may be not portable to other languages than C
  16. */
  17.  
  18. typedef struct nodo {
  19.   struct nodo *izq;
  20.   struct nodo *der;
  21.   int dato;
  22. }  *pnodo;
  23.  
  24. int sumar(const pnodo a)
  25. {
  26.   static int level = 0 ; // <== An eye to static qualifier (side effect!)
  27.   int suma=0;
  28.  
  29.   if(a!=NULL){
  30.     level++;  // <=== An eye.
  31.     suma=sumar(a->izq)+sumar(a->der);
  32.     level--; // <== An eye.
  33.     if ((a->izq!=NULL || a->der!=NULL) && level)  //  <=== An eye
  34. 	suma+=a->dato;
  35.   }
  36.   return suma;
  37. }
  38.  
  39.  
  40.  
  41. int main(int argc, char *args[])
  42. {
  43.   pnodo a=NULL;
  44.  
  45.  /* Raw building of tree. More abstraction might be needed here */
  46.   if ((a = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
  47.     {
  48.       perror("malloc");
  49.       exit(1);
  50.     }
  51.   a->dato = 10;
  52.   if ((a->izq = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
  53.     {
  54.       perror("malloc");
  55.       exit(1);
  56.     }
  57.   a->izq->dato = 5;
  58.   if ((a->izq->izq = (struct nodo* )malloc(sizeof(struct nodo)))==NULL)
  59.     {
  60.       perror("malloc");
  61.       exit(1);
  62.     }
  63.   a->izq->izq->dato = 3;  
  64.   if ((a->der = (pnodo )malloc(sizeof(struct nodo)))==NULL)
  65.     {
  66.       perror("malloc");
  67.       exit(1);
  68.     }
  69.   a->der->dato = 14;
  70.   if ((a->der->der = (pnodo )malloc(sizeof(struct nodo)))==NULL)
  71.     {
  72.       perror("malloc");
  73.       exit(1);
  74.     }
  75.   a->der->der->dato = 15;
  76.   if ((a->der->izq = (pnodo )malloc(sizeof(struct nodo)))==NULL)
  77.     {
  78.       perror("malloc");
  79.       exit(1);
  80.     }
  81.   a->der->izq->dato = 13;
  82.  
  83.   printf("Adding internal nodes %d\n",sumar(a));
  84.  
  85. }
  86.  
  87.  

Esta es la salida del programa
Código:
Adding internal nodes 19



Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines