Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 494 vistas

    Arboles Binarios de Búsqueda en C++

    Cargado por

    Taipe Lopez Andy
    Este documento describe los árboles binarios de búsqueda (ABB), incluidas sus definiciones y características. Explica que un ABB es un árbol binario donde los elementos menores se ubican en la rama izquierda y los mayores en la derecha, sin elementos repetidos. Luego detalla la estructura de nodos de un ABB en C++ y los tres tipos de recorridos posibles: preorden, inorden y postorden. Finalmente, presenta un código de ejemplo para crear e insertar nodos en un ABB, mostrarlo y

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Arboles Binarios de Búsqueda en C++

    Cargado por

    Taipe Lopez Andy
    494 vistas6 páginas
    Este documento describe los árboles binarios de búsqueda (ABB), incluidas sus definiciones y características. Explica que un ABB es un árbol binario donde los elementos menores se ubican en la rama izquierda y los mayores en la derecha, sin elementos repetidos. Luego detalla la estructura de nodos de un ABB en C++ y los tres tipos de recorridos posibles: preorden, inorden y postorden. Finalmente, presenta un código de ejemplo para crear e insertar nodos en un ABB, mostrarlo y

    Descripción original:

    c++

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe los árboles binarios de búsqueda (ABB), incluidas sus definiciones y características. Explica que un ABB es un árbol binario donde los elementos menores se ubican en la rama izquierda y los mayores en la derecha, sin elementos repetidos. Luego detalla la estructura de nodos de un ABB en C++ y los tres tipos de recorridos posibles: preorden, inorden y postorden. Finalmente, presenta un código de ejemplo para crear e insertar nodos en un ABB, mostrarlo y

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    494 vistas6 páginas

    Arboles Binarios de Búsqueda en C++

    Cargado por

    Taipe Lopez Andy
    Este documento describe los árboles binarios de búsqueda (ABB), incluidas sus definiciones y características. Explica que un ABB es un árbol binario donde los elementos menores se ubican en la rama izquierda y los mayores en la derecha, sin elementos repetidos. Luego detalla la estructura de nodos de un ABB en C++ y los tres tipos de recorridos posibles: preorden, inorden y postorden. Finalmente, presenta un código de ejemplo para crear e insertar nodos en un ABB, mostrarlo y

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 6

    Estructuras de Datos Dinmicas

    Arboles Binarios de Bsqueda en C++ [Recorrido por Niveles]


    Qu es un rbol?
    Un rbol es una estructura de datos no lineal puesto que cada elemento apunta a uno o varios
    elementos del mismo tipo; esto es dado un elemento, no hay un nico camino a seguir. El
    elemento que apunta a otro es llamado padre, mientras que el elemento apuntado se conoce
    como hijo. Todos los elementos tienen un padre a excepcin de la raz. Puede decirse que
    un rbol est formado por subarboles resaltando as su naturaleza recursiva.
    Qu es un rbol binario?
    Un ARBOL BINARIO es aquel es el que cada elemento apunta como mximo a otros 2 elementos,
    comnmente llamados hijo izquierdo y hijo derecho.

    Qu es un arbol binario de busqueda?


    Un arbol binario de buque da o ABB, es un arbol binario en el cual para todo elemento, los
    elementos mayores a l, se ubican en su rama derecha, mientras que los elementos menores
    van en su rama izquierda. Cada elemento se almacena una sola vez por lo que no existen
    elementos repetidos.

    Prof. Arturo Daz Pulido

    Estructuras de Datos Dinmicas

    Ya con estas definiciones claras sobre arboles;ahora estos son conceptos generales de lo que
    es un arbol, para poder implementarlos en lenguaje C++ tenemos que tener conocimientos
    previos sobre listas enlazadas y su implementacin.
    Cada elemento(nodo) de un rbol ABB cuenta con tres campos:
    - Dato(numero, letra, palabra, etc), en este caso usaremos un numero(entero).
    - Puntero al nodo derecho
    - Puntero al nodo izquierdo

    Los punteros tienen que ser del tipo arbol, ya que apuntaran a un nodo del mismo tipo, este
    seria un ejemplo de como se seria el tipo arbol ABB.
    Primero creamos el nodo:
    struct nodo{
    int dato;
    struct nodo *der;
    struct nodo *izq;
    };
    "Los punteros son variables que guardaran en la memoria la direccin de otra variable" en
    este caso la de una estructura llamado nodo.
    Recorridos de una arbol
    Es la manera recursiva como pasaremos por cada nodo del arbol, existes tres formas.

    Prof. Arturo Daz Pulido

    Estructuras de Datos Dinmicas


    Enorden: Si visitamos primero hijo izquierdo, luego el padre y finalmente el hijo derecho
    Preorden: Primero el padre, luego el hijo izquierdo y finalmente el hijo derecho.
    Postorden: Primero hijo izquierdo, luego el hijo derecho y finalmente el padre
    Existe muchos mas conceptos sobre arboles ABB por ejemplo, recorridos por nivel,
    profundidad de una arbol, etc; por ahora solo dejare esos conceptos.
    /*
    Inserta elemento, muestra el arbol, muestra los recorridos(enOrden,
    preOrden, postOrden)
    */
    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    struct nodo{
    int nro;
    struct nodo *izq, *der;
    };
    typedef struct nodo *ABB;
    /* es un puntero de tipo nodo que hemos llamado ABB, que ulitizaremos
    para mayor facilidad de creacion de variables */
    ABB crearNodo(int x)
    {
    ABB nuevoNodo = new(struct nodo);
    nuevoNodo->nro = x;
    nuevoNodo->izq = NULL;
    nuevoNodo->der = NULL;
    return nuevoNodo;
    }
    void insertar(ABB &arbol, int x)
    {
    if(arbol==NULL)
    {
    arbol = crearNodo(x);
    }
    else if(x < arbol->nro)

    Prof. Arturo Daz Pulido

    Estructuras de Datos Dinmicas


    insertar(arbol->izq, x);
    else if(x > arbol->nro)
    insertar(arbol->der, x);
    }
    void preOrden(ABB arbol)
    {
    if(arbol!=NULL)
    {
    cout << arbol->nro <<" ";
    preOrden(arbol->izq);
    preOrden(arbol->der);
    }
    }
    void enOrden(ABB arbol)
    {
    if(arbol!=NULL)
    {
    enOrden(arbol->izq);
    cout << arbol->nro << " ";
    enOrden(arbol->der);
    }
    }
    void postOrden(ABB arbol)
    {
    if(arbol!=NULL)
    {
    postOrden(arbol->izq);
    postOrden(arbol->der);
    cout << arbol->nro << " ";
    }
    }
    void verArbol(ABB arbol, int n)
    {
    if(arbol==NULL)

    Prof. Arturo Daz Pulido

    Estructuras de Datos Dinmicas


    return;
    verArbol(arbol->der, n+1);
    for(int i=0; i<n; i++)
    cout<<"

    ";

    cout<< arbol->nro <<endl;


    verArbol(arbol->izq, n+1);
    }
    int main()
    {
    ABB arbol = NULL;
    int n;

    // creado Arbol

    // numero de nodos del arbol

    int x; // elemento a insertar en cada nodo


    cout << "\n\t\t

    ..[ ARBOL BINARIO DE BUSQUEDA ]..

    cout << " Numero de nodos del arbol:

    \n\n";

    ";

    cin >> n;
    cout << endl;
    for(int i=0; i<n; i++)
    {
    cout << " Numero del nodo " << i+1 << ": ";
    cin >> x;
    insertar( arbol, x);
    }
    cout << "\n Mostrando ABB \n\n";
    verArbol( arbol, 0);
    cout << "\n Recorridos del ABB";
    cout << "\n\n En orden

    ";

    enOrden(arbol);

    cout << "\n\n Pre Orden

    ";

    preOrden(arbol);

    Prof. Arturo Daz Pulido

    Estructuras de Datos Dinmicas


    cout << "\n\n Post Orden :

    ";

    postOrden(arbol);

    cout << endl << endl;


    system("pause");
    return 0;
    }

    Ejercicios resueltos
    1. Escribir una funcin que devuelva el nmero de nodos de un rbol binario. Una
    solucin recursiva puede ser la siguiente:
    funcion nodos(arbol : tipoArbol) : devuelve entero;
    inicio
    si arbol = vacio entonces devolver 0;
    en otro caso devolver (1 + nodos(subarbol_izq) + nodos(subarbol_der));
    fin
    2. Implemente el recorrido de orden en un rbol: preorden, inorden y posorden.
    3. Desarrollar el rbol genealgico de una familia.

    Prof. Arturo Daz Pulido

    También podría gustarte