1

Estoy generando un árbol binario extrayendo los números de un archivo con el lenguaje C++, pero mi problema está en que quiero que solo se agreguen los números que no se repiten de dicho archivo. No se si me podrían ayudar con esto.....

Aquí dejo el código como referencia del programa que estoy haciendo. 

#include "stdafx.h"

#include "iostream"
#include "fstream"
#include "windows.h"
#include "stdlib.h"
#include <ctime>

using namespace std;

struct Nodo {
    int dato;
    Nodo *der;
    Nodo *izq;
    Nodo *padre;
};

Nodo *crearNodo(int, Nodo *);
void insertarNodo(Nodo *&, int, Nodo *);
void mostrarArbol(Nodo *, int);
void generarArbol();

Nodo *arbol = NULL;
ofstream escritura;
fstream lectura;
int cant = 0, num, vector[100], nodo = 0, contador = 0, cont = 0;

int auxX = 0;//Variable publica
void gotoxy(int x, int y)
{
    COORD c = { x, y };
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), c);
}

int main()
{
    generarArbol();

    cout << "Mostrando el arbol completo" << endl << endl;
    mostrarArbol(arbol, contador);
    cout << "\n\n";
    system("pause");
}

Nodo *crearNodo(int n, Nodo *padre) {
    Nodo *nuevo_nodo = new Nodo();

    nuevo_nodo->dato = n;
    nuevo_nodo->der = NULL;
    nuevo_nodo->izq = NULL;
    nuevo_nodo->padre = padre;

    return nuevo_nodo;
}

void insertarNodo(Nodo *& arbol, int n, Nodo *padre) {

    if (arbol == NULL) {
        Nodo *nuevo_nodo = crearNodo(n, padre);
        arbol = nuevo_nodo;
    }
    else {
        int valorRaiz = arbol->dato;
        cont = 0;
        if (n < valorRaiz) {
            insertarNodo(arbol->izq, n, arbol);
        }
        else {
            insertarNodo(arbol->der, n, arbol);
        }
    }
}

void mostrarArbol(Nodo *arbol, int cont) {
    if (arbol == NULL) {
        return;
    }
    else {
        mostrarArbol(arbol->der, cont + 1);
        for (int i = 0; i < cont; i++) {
            cout << "   ";
        }
        cout << arbol->dato << endl;
        mostrarArbol(arbol->izq, cont + 1);

    }
}

void generarArbol() {
    lectura.open("arbol.txt", ios::in);

    if (lectura.is_open()) {
          lectura >> nodo;
          insertarNodo(arbol, nodo, NULL);
        while (!lectura.eof()) {    
            lectura >> nodo;
            insertarNodo(arbol, nodo, NULL);
        }
        lectura >> nodo;
    }
    else {
        cout << "Error! Archivo no existe " << endl;
    }
    lectura.close();
    system("pause");
}

¿Tal vez la solución pueda ser desde el código de la función insertarNodo? O sería mas sencillo hacer la validación con el archivo? Espero puedan ayudarme ¡muchas gracias!

PaperBirdMaster
  • 44,474
  • 6
  • 44
  • 82
user73355
  • 41
  • 4

2 Answers2

5

Estube intentando resolver tu problema, y la solución estaria en agregar una condicional if(n != arbol->dato) en la función insertarNodo.

void insertarNodo(Nodo *& arbol, int n, Nodo *padre)
{
    if (arbol == NULL)
    {
        Nodo *nuevo_nodo = crearNodo(n, padre);
        arbol = nuevo_nodo;
    }
    else if(n != arbol->dato) // Aqui es donde se comprueba que no haya repetición
    {
        if (n < arbol->dato) {
            insertarNodo(arbol->izq, n, arbol);
        }
        else {
            insertarNodo(arbol->der, n, arbol);
        }
    }
}

Lo probé con un archivo "arbol.txt" con la siguiente secuencia:

1 2 3 4 7 2 4 5 8 4

Me da el siguiente resultado: introducir la descripción de la imagen aquí

Germán Martínez
  • 1,057
  • 1
  • 9
  • 16
  • era tan simple la solución? me siento tan sorprendido como avergonzado por lo sencillo que era jajaja. **Muchas gracias!** lo probe en mi programa y funciona bien – user73355 Mar 27 '18 at 00:29
  • 1
    @user73355 si esta respuesta soluciona tu problema, por favor, márcala como solución. – eferion Mar 27 '18 at 06:33
0

Como ya ha señalado Germán Martínez, la solución pasa por verificar si el dato existe antes de su inserción; yo no puedo aportar una solución diferente, pero sí que te puedo sugerir muchas mejoras a tu código.

Cosas a tener en cuenta.

Estás etiquetando la pregunta como y es correcto porque utilizas el operador new (exclusivo de C++) y la salida por consola std::cout.

Si quieres programar en C++ usando las cabeceras de C, debes usar las versiones adaptadas a C++, en tu caso <cstdlib> en lugar de <stdlib.h>, lee este hilo para saber más al respecto. Lo has hecho bien con <ctime> pero no usas ninguna de sus utilidades en todo el código.

No uses variables globales:

  • Carecen de localidad: El código es más fácil de comprender cuando su ámbito es limitado. Las variables globales pueden ser leídas o modificadas desde cualquier parte del programa, esto hace difícil razonar sobre su uso o recordar todos los puntos en que se usan.
  • Carecen de control de acceso o verificación de restricciones: Una variable global puede ser leída o escrita desde cualquier parte del programa, varias reglas acerca de su uso pueden ser olvidadas o violadas.
  • Problemas de concurrencia: Si las variables globales pueden ser accedidas desde varios hilos, es necesario sincronizarlas. Cuando se trabaja con módulos dinámicamente enlazados que usan variables globales, el sistema resultante puede no ser seguro incluso cuando los módulos lo sean de manera independiente.
  • Contaminación del espacio de nombres: Las variables globales están en todos los contextos. Puedes acabar usando una variable global cuando creías estar usando una local ¡o viceversa! (ya sea por desconocimiento, escribir mal el nombre u olvidarte de crear la variable local). Además, si enlazas módulos con variables globales cuyo nombre sea igual, si tienes suerte, tendrás errores de enlazado... si no tienes suerte el enlazador considerará las variables como la misma incluso aunque no fuese tu intención.
  • Más problemas en el enlace (en Inglés): He traducido los puntos que creía que eran más relevantes para tu problema.

Sigue los principios de encapsulamiento; ahora mismo tu código se basa en variables y funciones globales, muchas de las cuales no tiene sentido que sean accesibles por el usuario; uno de los principios del encapsulamiento es precisamente mantener oculto (o inaccesible) lo que se use internamente y sólo mantener accesible lo necesario para el buen uso del programa.

Como analogía, imagina un coche: la carrocería te oculta los elementos internos como el motor, la batería, la caja de cambios, los ejes, etcétera...

Mmm... me pregunto qué pasará si le pego un lametón a la junta de la trócola.

No necesitas saber que esos elementos están ahí para usar el coche (no necesitas siquiera verlos) lo único que necesitas saber es dónde están los pedales, la palanca de cambios y el contacto.

De hecho, es probable que tú o cualquiera que use el coche tenga la tentación de manipular los elementos que tenga accesibles, con la posibilidad de derivar en un uso incorrecto de los mismos, cuantas más cosas se puedan manipular más probabilidades hay de que sean manipuladas de manera incorrecta.

Confundes nodos y árboles, he visto en StackOverflow en Español varias veces esta confusión, y me resulta muy curioso que tantos usuarios cometan ese error.

En el código que has facilitado se usa la variable de nombre arbol cuyo tipo subyacente es un Nodo *. Y eso es tan erróneo como decir que un escalón es una escalera, sinceramente ¿Te parecen lo mismo?:

Corrigiendo los problemas mencionados, tu código podría quedar así:

// Un objeto árbol, no variables sueltas.
struct Arbol {

    // Interesa insertar datos, el como se inserten no es de interés para el usuario
    void insertar(int dato) {
        // Las condiciones positivas son más intuitivas
        if (raiz) {
            insertarNodo(raiz, dato, nullptr);
        }
        else {
            // Nodo es un agregado, puede crearse así.
            raiz = new Nodo{dato};
        }
    }

    void mostrar() {
        mostrar_recursivo(raiz);
    }

private:
    // El nodo forma parte del árbol, no tiene sentido que sea accesible fuera
    // Los valores por defecto evitan sorpresas.
    struct Nodo {
        int dato = 0;
        Nodo *der = nullptr;
        Nodo *izq = nullptr;
        Nodo *padre = nullptr;
    };

    // El árbol tiene una raíz, de la que parten el resto de nodos
    Nodo *raiz = nullptr;

    // En la zona PRIVADA, el usuario no tiene por qué acceder a los datos internos.
    void insertarNodo(Nodo *& nodo, int dato, Nodo *padre) {
        // Las condiciones positivas son más intuitivas
        if (nodo) {
            if (dato != nodo->dato)
            {
                insertarNodo((dato < nodo->dato) ? nodo->izq : nodo->der, dato, nodo);
            }
        }
        else {
            // Nodo es un agregado, puede crearse así.
            nodo = new Nodo{dato, nullptr, nullptr, padre};
        }
    }

    void mostrar_recursivo(Nodo *& nodo) {
        // Usa el algoritmo que prefieras...
        std::cout << nodo->dato << '\n';
        if (nodo->izq) {
            mostrar_recursivo(nodo->izq);
        }
        if (nodo->der) {
            mostrar_recursivo(nodo->der);
        }
    }
};

Esto se puede usar así:

Arbol a;
a.insertar(1);
a.insertar(2);
a.insertar(3);
a.insertar(4);
a.insertar(7);
a.insertar(2);
a.insertar(4);
a.insertar(5);
a.insertar(8);
a.insertar(4);
a.mostrar();

Recuerda que falta borrar los datos (tanto en este código como en el que muestras).

PaperBirdMaster
  • 44,474
  • 6
  • 44
  • 82