16.4. Insertar nodos en un árbol ABB

Primero creamos el nodo.

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

Creamos el nuevo Nodo en una función externa.

Nodo *crearNodo(int n){
    Nodo *nuevo_nodo = new Nodo();
    nuevo_nodo->dato = n;
    nuevo_nodo->der = NULL;
    nuevo_nodo->izq = NULL;
    return nuevo_nodo;
}

Comenzamos con la función insertar

Ahora para insertar un nodo en el árbol necesita tener en cuenta:

void insertar(Nodo *&arbol, int n){
    //...
}

El árbol puede estar vacío

if(arbol == NULL){
    Nodo *nuevo_nodo = crearNodo(n);
    arbol = nuevo_nodo;
}

Ya tendríamos nuestro nodo raíz

El árbol ya tiene un nodo o más

else{
    int valorRaiz = arbol->dato;
    if(n < valorRaiz){
        //Se coloca a la izquierda
        insertar(arbol->izq,n);
    }
    else{
        //Se coloca a la derecha
        insertar(arbol->der,n)
    }
}

Notese que es una función recursiva, vea [[Informática/Programación/C++/11. Funciones]]

Código Completo

//Librerias
#include<iostream>
#include<stdlib.h>
#include<conio.h>
using namespace std;

//Estructura
struct Nodo{
    int dato;
    Nodo *der;
    Nodo *izq;
};

//Prototipos de Función
Nodo *crearNodo(int);
void insertarNodo(Nodo *&, int);
void menu();

//Variables globales
Nodo *raiz = NULL;

//Función Principal
int main(){
    menu();
    return 0;
}

//Funciones
void menu(){
    int dato, opc;

    do{
        cout<<".:MENU:."<<endl;
        cout<<"1. Insertar un elemento"<<endl;
        cout<<"0. Salir del programa"<<endl;
        cout<<"Digite su opcion: "; cin>>opc;

        switch (opc){
            case 1:
                cout<<"\n\tDigite un numero: "; cin>>dato;
                insertarNodo(raiz, dato);
                cout<<"\n";
                system("pause");
            break;
        }
        system("cls");
    }while(opc != 0);
}

Nodo *crearNodo(int n){
    Nodo *nuevo_nodo = new Nodo();
    nuevo_nodo -> dato = n;
    nuevo_nodo -> izq = NULL;
    nuevo_nodo -> der = NULL;

    return nuevo_nodo;
}

void insertarNodo(Nodo *&raiz, int n){
    if(raiz == NULL){  //El padre está vacío
        Nodo *nuevo_nodo = crearNodo(n);  //raiz = crearNodo(n);
        raiz = nuevo_nodo;
    }
    else{
        if(raiz -> dato < n){
            //Insertar a la izquierda
            insertarNodo(raiz -> izq, n);
        }
        else{
            //Insertar a la derecha
            insertarNodo(raiz -> der, n);
        }
    }
}

Nota: En la función insertarNodo una forma equivalente es:

    if(raiz == NULL){  //El padre está vacío
        raiz = crearNodo(n);
    }