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


 


Tema destacado: Deseas probar algunas mejoras a la interfaz del foro? Prueba cake! acerca de


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse)
| | |-+  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 269 veces)
Beginner Web

Desconectado Desconectado

Mensajes: 285


youtu.be/0YhflLRE-DA


Ver Perfil
Recursion en bst
« en: 12 Enero 2019, 01:59 »

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 por Beginner Web » En línea

Código
  1. #Programadora: Ana Kéldysh
  2. #Edad: 14 años
  3. #!/bin/bash
  4. echo Hola
CalgaryCorpus

Desconectado Desconectado

Mensajes: 246


Ver Perfil
Re: Recursion en bst
« Respuesta #1 en: 12 Enero 2019, 04:07 »

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 por CalgaryCorpus » En línea

dijsktra

Desconectado Desconectado

Mensajes: 62


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Recursion en bst
« Respuesta #2 en: 17 Enero 2019, 14:35 »

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 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: 285


youtu.be/0YhflLRE-DA


Ver Perfil
Re: Recursion en bst
« Respuesta #3 en: 18 Enero 2019, 23:37 »

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

Código
  1. #Programadora: Ana Kéldysh
  2. #Edad: 14 años
  3. #!/bin/bash
  4. echo Hola
MAFUS


Desconectado Desconectado

Mensajes: 1.410



Ver Perfil
Re: Recursion en bst
« Respuesta #4 en: 19 Enero 2019, 21:01 »

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

while(is_alive(yourself)) {
    make_true(yourself, yourdreams);
}
Beginner Web

Desconectado Desconectado

Mensajes: 285


youtu.be/0YhflLRE-DA


Ver Perfil
Re: Recursion en bst
« Respuesta #5 en: 19 Enero 2019, 21:09 »

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

Código
  1. #Programadora: Ana Kéldysh
  2. #Edad: 14 años
  3. #!/bin/bash
  4. echo Hola
dijsktra

Desconectado Desconectado

Mensajes: 62


Mr Edsger Dijsktra (Tribute to)


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

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 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
Recursion+Factorial desde 1-10
Programación C/C++
d4rkzone 8 2,768 Último mensaje 21 Septiembre 2008, 14:04
por Ragnarok
gramatica sin recursión a la izquierda
Dudas Generales
m@o_614 0 495 Último mensaje 5 Septiembre 2014, 03:52
por m@o_614
Java Recursion
Java
josephb401 2 579 Último mensaje 3 Diciembre 2015, 19:00
por josephb401
Ayuda con recursion!!!!
Java
rociodyj 0 563 Último mensaje 23 Octubre 2017, 23:24
por rociodyj
Recursión
Java
padiuwu 1 75 Último mensaje 18 Marzo 2019, 20:36
por spcruzaley
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines