¿Cómo puedo Definir el Nodo Raíz de un Árbol?

Question

Estoy creando un programa para alojar en un Árbol los CURP que genere mi programa, pero, como bien sabemos, hay un criterio en la generación de los CURP, el cuál es que los 2 últimos dígitos de nuestro CURP si nacimos antes del año 2000 se nos asignarán 2 dígitos, pero, si nacimos después del año 2000 se nos asignará una letra y un dígito.

Lo que quiero hacer es:

Definir el nodo Raíz de mi árbol con valor 2000, para que así cuando el usuario digite su año de nacimiento, pueda evaluarlo y se decida si su curp se enviará al sub-árbol izquierdo que van los CURP menores al año 2000 o al sub-árbol derecho que van los CURP mayores al año 2000.

Al momento de llamar a mi método impirmirArbol no me imprime nada. Les dejo un código prueba que estoy haciendo, para imprementar a mi código que genera los CURP.

#include<iostream>
#define TAM 20
using namespace std;

struct Nodo
{
    char dato[TAM];
    int valor;
    Nodo *der;
    Nodo *izq;
};
Nodo *arbol=NULL;
void Menu();
Nodo *crearNodo(char[]);
void insertarNodo(Nodo *&,int,char[]);
void mostrarArbol(Nodo *,int);

int main()
{
    Menu();
    return 0;
}

void Menu()
{
    int op;
    char c[TAM];
    int v;
    int cont=0;
    do
    {
        cout<<"\t\t Menu"<<endl;
        cout<<"1.- Agregar Nodo"<<endl;
        cout<<"2.- Mostrar Arbol"<<endl;
        cout<<"9.- SALIR"<<endl;
        cout<<"Digite su opcion: ";
        cin>>op;
        switch (op)
        {
            case 1:
                {
                    cout<<"Digite un valor: ";
                    cin>>v; //Supongamos que es el año de nacimiento
                    cout<<"Escriba una Cadena de caracteres: ";
                    cin>>c; //Supongamos que es su CURP
                    insertarNodo(arbol,v,c); //Le envio al Metodo insertarNodo el arbol para saber si ya tengo más nodos o no. acompañado de su año de nacimiento para evaluar si se va al sub arbol derecho o izquierdo y por últtimo su CURP, para poder imprimirlo en el arbol
                }
            break;
            case 2:
                {
                    cout<<"Mostrando el arbol"<<endl;
                    mostrarArbol(arbol,cont); // No me imprime nada
                }
            break;
        }
        system("PAUSE");
        system("CLS");
    }while(op!=9);
}

Nodo *crearNodo(char n[])
{
    Nodo *nuevoNodo = new Nodo();
    nuevoNodo->dato[TAM]=n[TAM];
    nuevoNodo->der=NULL;
    nuevoNodo->izq=NULL;
}

void insertarNodo(Nodo *&arbol,int val,char n[])
{
    if(arbol==NULL)
    {
        Nodo *nuevoNodo= crearNodo(n);
        arbol=nuevoNodo;
    }
    else
    {
        int valorRaiz=arbol->valor;
        valorRaiz=2000;
        if(val<valorRaiz)
        {
            insertarNodo(arbol->izq,val,n);
        }
        else
        {
            insertarNodo(arbol->der,val,n);
        }
    }
}

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

Answer 1

Deberías empezar por leer esta pregunta:

• Tengo una lista simplemente enlazada ¿Cómo le añado datos?.

Se que la pregunta va de listas (no árboles) pero estás cometiendo el mismo error que se comete en varias preguntas de la misma naturaleza que encontramos en este sitio: Un nodo no es un árbol de la misma manera que un escalón no es una escalera.

---

Por otro lado, comentas que tu problema está en la función impirmirArbol, la cuál no compartes. ¿Tal vez te referías a la función mostrarArbol?

Sea como sea, confundes métodos con funciones. La función mostrarArbol no es un método porque no pertenece a ningún objeto.

---

Para acabar, es normal que no se muestre nada al mostrar tu árbol porque no copias en el nodo los datos que quieres insertar. La función de creación de nodo es incorrecta:

Nodo *crearNodo(char n[])
{
    Nodo *nuevoNodo = new Nodo();
    nuevoNodo->dato[TAM]=n[TAM]; // ¡¡¡ERROR!!!
    nuevoNodo->der=NULL;
    nuevoNodo->izq=NULL;
}

La variable Nodo::dato es una formación ¹ de 20 (TAM) caracteres (char). La orden nuevoNodo->dato[TAM]=n[TAM]; lo que hace es copiar el elemento que esté en la posición 20 de n en la posición 20 de nuevoNodo->dato, que además, como las formaciones de C++ se indexan desde 0, será una posición incorrecta (la posición máxima es 19). Para copiar formaciones de datos debes utilizar una función de copia:

Nodo *crearNodo(char n[])
{
    Nodo *nuevoNodo = new Nodo();
    std::copy(n, n + TAM, nuevoNodo->dato);
    nuevoNodo->der=NULL;
    nuevoNodo->izq=NULL;
}

Date cuenta también que no estás copiando Nodo::valor.

Propuesta.

Estás programando en C++, programa orientado a objetos:

• Crea un objeto árbol, no crees un nodo que tratarás como árbol.
• Otorga constructores a los objetos o usa inicialización uniforme.
• Que los métodos sean métodos, no funciones sueltas.
• Usa std::string en lugar de char[TAM].

Teniendo en cuenta estos consejos, tu árbol podría quedar así:

struct Arbol
{
    void inserta(int valor, std::string dato);
    void muestra();

private:

    void inserta(nodo *&origen, nodo *&nuevo_nodo);

    struct nodo
    {
        int valor = 0;
        std::string dato = "";
        nodo *der = nullptr;
        nodo *izq = nullptr;
    };

    nodo *raiz = nullptr;
};

La estructura nodo forma parte del árbol como tipo privado, pues siguiendo los principios de encapsulamiento, no hay ninguna necesidad de que este tipo de dato sea accesible fuera del árbol. La función de inserción ya no recibe el nodo en el que insertar pues será el árbol (no el usuario del árbol) el que se encargue de controlar los nodos, por ese mismo motivo la función de inserción tiene una sobrecarga privada, que es la que se encargará de hacer el trabajo interno, la definición de estas funciones podría quedar así:

void Arbol::inserta(int valor, std::string dato)
{
    inserta(raiz, new nodo{valor, dato})
}

void Arbol::inserta(nodo *&origen, nodo *&nuevo_nodo)
{
    if (origen)
    {
        inserta(nuevo_nodo->valor < 2000 ? origen->izq : origen->der, nuevo_nodo);
    }
    else
    {
        origen = nuevo_nodo;
    }
}

Es la sobrecarga pública de Arbol::inserta la que crea el nodo, el cuál obtiene directamente sus datos mediante inicialización uniforme, este nodo recién creado viajará por el árbol hasta encontrar un nodo origen que sea nulo y se alojará ahí.

Problema.

En mi propuesta he seguido tu algoritmo de inserción pero es completamente incorrecto, todos los nodos menores a 2000 se pondrán siempre en ramas izquierdas y todos los nodos mayores a 2000 se pondrán siempre en ramas derechas; suponiendo que insertamos (en orden) los valores de 1995 a 2003 tu árbol tendrá este aspecto:

---

---

Si quieres seguir tu premisa, la clase Arbol podría tener este aspecto:

struct Arbol
{
    void inserta(int valor, std::string dato);
    void muestra();

private:

    void inserta(nodo *&origen, nodo *&nuevo_nodo);

    struct nodo
    {
        int valor = 0;
        std::string dato = "";
        nodo *der = nullptr;
        nodo *izq = nullptr;
    };

    nodo raiz{2000};
//  ~~~~ <--- La raíz es una instancia (no un puntero) con valor 2000.
};

Dado que la raíz ya no es un puntero, el método público de inserción tendría esta definición:

void Arbol::inserta(int valor, std::string dato)
{
    auto origen = &raiz; // Obtenemos la dirección de la raíz.
    auto nuevo_nodo = new nodo{valor, dato};
    inserta(origen, nuevo_nodo);
}

Y la inserción de datos ya no debería basarse en si el valor a insertar es mayor o menor a 2000 si no si el valor es mayor o menor al nodo candidato:

void Arbol::inserta(nodo *&origen, nodo *&nuevo_nodo)
{
    if (origen)
    {
        inserta(nuevo_nodo->valor < origen->valor ? origen->izq : origen->der, nuevo_nodo);
//              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ <--- ¿El nodo candidato es menor al nodo
//                                                     de origen? izq, si no: der.
    }
    else
    {
        origen = nuevo_nodo;
    }
}

---

1. También conocida como "arreglo", o "array" en inglés.