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

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


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


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Recursion en bst
« 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. }


« Última modificación: 12 Enero 2019, 02:48 am por Beginner Web » En línea

7w7
CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: Recursion en bst
« Respuesta #1 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.


« Última modificación: 12 Enero 2019, 15:13 pm por CalgaryCorpus » En línea

Aqui mi perfil en LinkedIn, invitame un cafe aqui
dijsktra

Desconectado Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Recursion en bst
« Respuesta #2 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.  
« Última modificación: 17 Enero 2019, 14:41 pm por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Re: Recursion en bst
« Respuesta #3 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.  :-(
En línea

7w7
MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: Recursion en bst
« Respuesta #4 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.
En línea

Beginner Web


Desconectado Desconectado

Mensajes: 634


youtu.be/0YhflLRE-DA


Ver Perfil
Re: Recursion en bst
« Respuesta #5 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
En línea

7w7
dijsktra

Desconectado Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Recursion en bst
« Respuesta #6 en: 21 Enero 2019, 10:47 am »

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

« Última modificación: 21 Enero 2019, 11:14 am por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
gramatica sin recursión a la izquierda
Dudas Generales
m@o_614 0 1,459 Último mensaje 5 Septiembre 2014, 03:52 am
por m@o_614
Java Recursion
Java
josephb401 2 1,685 Último mensaje 3 Diciembre 2015, 19:00 pm
por josephb401
Problema de Backtracking (recursion)
Programación C/C++
KINGARZA 0 2,210 Último mensaje 6 Julio 2017, 08:17 am
por KINGARZA
Ayuda con recursion!!!!
Java
rociodyj 0 2,144 Último mensaje 23 Octubre 2017, 23:24 pm
por rociodyj
Recursión
Java
padiuwu 1 1,636 Último mensaje 18 Marzo 2019, 20:36 pm
por spcruzaley
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines