0

Buenas. Tengo un problema con mi código en c++, el caso es que necesito implementar un campeonato deportivo usando arboles, como en el siguiente ejemplo:

introducir la descripción de la imagen aquí

En la imagen de ejemplo, Piston y Magics son dos equipos deportivos de baloncesto, piston gano con un total de 115 puntos y Magics con un total de 95 puntos. Los que lo subsiguen son los demás equipos, que corresponderán a aquellos equipos los cuales tendrán que tener un juego con dicho equipo que gano o perdio. En la imagen de ejemplo el total de equipos son 8. Yo necesito hacer un código con 16 equipos en total usando arboles.

Yo lo que llevo es lo siguiente, que es basicamente pedirle los datos respectivos que necesito al usuario:

#include<iostream>

using namespace std;

int main(){
    char fecha;
    string lugar;
    char equipo1;
    char equipo2;
    int puntosequipo1;
    int puntosequipo2;

    for (int i=0;i<16;i++){
        cout<<"Fecha del encuentro"<<endl;
        cin>>fecha;
        cout<<endl<<endl;
        cout<<"Lugar del encuentro"<<endl;
        cin>>lugar;
        cout<<endl<<endl;
        cout<<"Codigo del equipo 1"<<endl;
        cin>>equipo1;
        cout<<endl<<endl;
        cout<<"Codigo del equipo 2"<<endl;
        cin>>equipo2;
        cout<<endl<<endl;
        cout<<"Puntos del equipo 1"<<endl;
        cin>>puntosequipo1;
        cout<<endl<<endl;
        cout<<"Puntos equipo 2"<<endl;
        cin>>puntosequipo2;
        cout<<endl<<endl;
    }
}

Cada nodo del árbol debe almacenar la información de un partido, de acuerdo a la información recopilada por encuentro, y debo utilizar para el almacenamiento inicial (en la captura de datos) una estructura de datos tipo arreglo. El nodo raíz del arbol indicará el equipo ganador del campeonato. Y entre las normas del campeonato se tiene que ningún juego puede terminar empatado, así que en esos casos se prolongará con tiempos extras de 5 minutos cada uno hasta que ocurra un desempate.

Necesito que mi código utilizando use estructuras de árbol con almacenamiento dinámico, imprima los equipos del campeonato que no ganaron ningún partido, imprima el número de niveles del árbol, imprima cada nodo con su respectivo hijo izquierdo y derecho, y finalmente indique el tipo de recorrido utilizado. Agradecería mucho sus respuestas

1 respuesta 1

1

Estás programando en C++, no en C, luego esto:

struct nodo{
     int nro;
     struct nodo *izq, *der;
};

debería quedar así:

struct nodo{
     int nro;
     nodo *izq, *der;
};

Y por supuesto esto:

typedef struct nodo *ABB;

sobra o, al menos, considera asignar un alias un poco más significativo. Pero desde luego según lo expuesto en tu comentario:

/* es un puntero de tipo nodo que hemos llamado ABB, que ulitizaremos
   para mayor facilidad de creacion de variables */

El alias no tiene sentido ya que al menos yo no veo ninguna ventaja al usar ABB respecto a nodo*.

La creación de nuevos elementos debería quedar así:

nodo* nuevoNodo = new nodo;

en vez de así:

ABB nuevoNodo = new(struct nodo);

Y bueno, hablando de creación de elementos, en C++ toda clase o estructura tiene una serie de constructores asociados (si no los implementas manualmente el compilador genera una versión implícita). En tu caso te vendría muy bien para dejar el código más claro:

struct nodo
{
  explicit nodo(int x)
    : nro(x),
      izq(0), // C++11 en adelante puede quedar asi izq(nullptr)
      der(0)
  { }
};

Con lo que la función crearNodo quedaría entonces así:

nodo* crearNodo(int x)
{
  return new nodo(x);
}

Y lo mismo ya no es ni necesaria dicha función.

Nota: explicit se usa en este caso para evitar que las conversiones implícitas te puedan jugar una mala pasada. Este modificador hace que únicamente se pueda invocar a este constructor si se indica de forma expresa. Sin explicit podrías hacer lo siguiente (y no parece muy adecuado):

void funcTest(nodo)
{ /* ... */ }

funcTest(5);    

Y para rematar la faena hablar de las tareas de limpieza de memoria. Todo new debería tener su correspondiente delete y en tu código no hay una sola operación de limpieza.

Dado que los nodos están anidados podría tener sentido asumir que eliminar el nodo padre debería conllevar la eliminación automática de sus dos hijos. Esto provocaría una reacción en cascada que liberaría toda la memoria reservada de forma recursiva. Lo más común es implementar el destructor correspondiente:

struct nodo
{
  ~nodo()
  {
    delete izq;
    delete der;
  }
};

Bueno, dicho esto podemos continuar. Se supone que cada nodo debe guardar el resultado de un encuentro entre dos equipos, es decir:

  • cada nodo almacena el nombre de dos equipos
  • cada nodo almacena un resultado

Es decir, tu código podría tener algo tal que:

// Acostumbro a poner la primera en mayusculas para las clases
// y las estructuras
struct Nodo
{
  std::string local;
  std::string visitante;
  int golesLocal;
  int golesVisitante;

  Nodo* izq;
  Nodo* der;
};

Aunque yo personalmente preferiría separar la lógica del árbol del contenido del mismo:

struct Item
{
  std::string local;
  std::string visitante;
  int golesLocal;
  int golesVisitante;
};

struct Nodo
{
  Item datos;

  Nodo* izq;
  Nodo* der;
};

Con esto ya podrías empezar a trabajar en el árbol. Ahora bien, dado que podemos asumir que todos los partidos se van a disputar y que las eliminatorias son completas (dos semifinales, 4 cuartos, 8 octavos, etc...), el árbol podría crearse en el momento en el que se conoce el número de eliminatorias. Una forma sencilla de conseguirlo es con algo así:

Nodo* CrearTorneo(int niveles)
{
  Nodo* partido = 0; // Si compilas en C++11 o superior usa mejor nullptr

  if( niveles > 0 )
  {
    partido = new Nodo;
    partido->izq = CrearTorneo(niveles-1);
    partido->der = CrearTorneo(niveles-1);
  }

  return partido;
}

Podemos asumir, por ejemplo, que el partido no se ha disputado si los nombres de los equipos están en blanco. Como para almacenar los nombres hemos usado std::string no hace falta que nos preocupemos por inicializar su valor ya que por defecto será una cadena vacía.

Bien, ahora toca rellenar las eliminatorias e imprimir el árbol... eso corre de tu cuenta.

¿Cómo imprimir el número de niveles?

Itera por una de las ramas del árbol y por cada elemento que te encuentres tendrás un nivel. También puedes almacenar el número de niveles al principio en una variable... ignoro el margen de maniobra que tienes.

¿Cómo encontrar qué equipos no ganaron ningún partido?

Lo más sencillo sería ir a la base del árbol y recoger el nombre de aquellos equipos que perdieron esa eliminatoria (se supone que a segunda ronda únicamente pasan aquellos que ganan el primer partido).

Se puede calcular muy fácilmente de forma recursiva:

void ImprimirEquiposSinVictorias(Nodo* raiz)
{
  if( raiz->der )
  {
    ImprimirEquiposSinVictorias(raiz->der);
    ImprimirEquiposSinVictorias(raiz->izq);
  }
  else
  {
    if( raiz->datos.golesLocal > raiz->datos.golesVisitante )
      std::cout << raiz->datos.visitante;
    else
      std::cout << raiz->datos.local;
  }
}
4
  • También le falta el retorno de main :( el 3 abr. 2017 a las 6:46
  • @PaperBirdMaster cierto
    – eferion
    el 3 abr. 2017 a las 7:13
  • Gracias por la respuesta, pero aún soy muy principiante y no comprendo muy bien por la complejidad de la respuesta y lo generalizada que esta, aún así gracias. Con respecto a la otra pregunta que hice similar, no es que haya ignorado la respuesta de esta pregunta, si no que no la llegue a entender porque soy principiante y quería optar a ver si alguien podría explicarla de una manera manera más facil. el 3 abr. 2017 a las 15:21
  • @GreciaV.P.Valero o vienes de C o has aprendido C++ a través de un curso de C. La primera parte de la respuesta te comento detalles que no son errores pero si son atípicos en C++. Por otro lado si no eres capaz de entender el tema de la estructura lo que necesitas no es que te la expliquen de manera más facil sino que necesitas ponerte las pilas a estudiar y comprender el lenguaje C++. No es un desprecio sino una crítica constructiva
    – eferion
    el 3 abr. 2017 a las 15:30

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.