Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 376 vistas

    Rodrigo Guzmán Tarea 8

    Cargado por

    Guzmán Reyes
    Este documento describe la construcción de un árbol binario de búsqueda utilizando 20 nodos dados. Explica los pasos para insertar cada nodo en el árbol siguiendo las reglas de un árbol binario. También describe cómo realizar un recorrido preorden en este árbol binario de búsqueda.

    Copyright:

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

    Rodrigo Guzmán Tarea 8

    Cargado por

    Guzmán Reyes
    376 vistas10 páginas
    Este documento describe la construcción de un árbol binario de búsqueda utilizando 20 nodos dados. Explica los pasos para insertar cada nodo en el árbol siguiendo las reglas de un árbol binario. También describe cómo realizar un recorrido preorden en este árbol binario de búsqueda.

    Descripción original:

    Estructura de datos, Árboles. IACC semana 8.

    Título original

    Rodrigo_Guzmán_tarea_8

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe la construcción de un árbol binario de búsqueda utilizando 20 nodos dados. Explica los pasos para insertar cada nodo en el árbol siguiendo las reglas de un árbol binario. También describe cómo realizar un recorrido preorden en este árbol binario de búsqueda.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    376 vistas10 páginas

    Rodrigo Guzmán Tarea 8

    Cargado por

    Guzmán Reyes
    Este documento describe la construcción de un árbol binario de búsqueda utilizando 20 nodos dados. Explica los pasos para insertar cada nodo en el árbol siguiendo las reglas de un árbol binario. También describe cómo realizar un recorrido preorden en este árbol binario de búsqueda.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    de 10

    “Árboles”

    Rodrigo Andrés Guzmán Farías

    Estructura de datos

    Instituto IACC

    30/12/2019
    Desarrollo

    1.- Usando los siguientes datos construya un árbol binario de búsqueda y grafíquelo
    utilizando la herramienta que estime conveniente e insértelo en su documento (describa
    paso a paso su construcción). (3 puntos)
    Nodos: 22, 15, 3, 8, 40, 45, 13, 20, 30, 1, 7, 34, 48, 53, 9, 23, 12, 51, 4, 10.
    R:

    De acuerdo al material proporcionado por IACC para el desarrollo de las actividades de la


    semana, puedo explicar la construcción de este árbol de tipo binario de la siguiente manera:

    Se conoce como árbol binario a aquellos árboles ordenados de grado dos, ya que como principal
    característica esta en que cada nodo de la estructura no poseerá más de dos descendientes
    directos. Las aplicaciones que puedan realizar los árboles de tipo binario varían, ya que es
    posible utilizarlos para poder representar una estructura en la cual podamos tomar decisiones
    manejando dos opciones en puntos distintos.
    Sera posible representar de dos formas un árbol binario en memoria:
    1. A través de datos tipo punteros, conocidos también como variables dinámicas o listas.
    2. A través de arreglos.

    En cuanto a los nodos de esta estructura, estos serán representados como registros los cuales
    deben contener tres campos como mínimo. En uno se ha de almacenar la información del nodo,
    y los otros dos serán usados para apuntar al subárbol izquierdo y subárbol derecho.

    Para realizar un recorrido en un árbol binario es posible realizarlo de tres formas: en inorden,
    preorden y postorden.

    Para construir este árbol binario utilice los siguientes pasos:

    - Tenemos un árbol “vacío”, por lo tanto, para crear espacio en memoria debemos insertar
    nuestro primer nodo el cual será la “raíz” de nuestra estructura. He decidido insertar los nodos
    en le mismo orden en que fueron presentados en guía (22, 15, 3, 8, 40, 45, 13, 20, 30, 1, 7, 34,
    48, 53, 9, 23, 12, 51, 4, 10). Por lo tanto, el nodo raíz será el nodo 22, teniendo establecido este
    punto, es posible la creación de nuevos vértices en la estructura, siguiendo los parámetros que
    corresponden a un árbol binario, en donde cada nodo solo puede poseer dos hijos descendientes y
    que también siempre el valor ubicado a la izquierda debe ser menor al nodo raíz y menor a cada
    nodo padre que presente la estructura. De igual forma, a la derecha del nodo raíz se ubicarán
    solamente los nodos mayores a la raíz y en caso de los nodos padres aplica la misma lógica.

    - Inserto el resto de los nodos:


    -(Raíz 22).
    -15 a la izquierda de 22.
    - 3 a la izquierda de 15.
    - 8 a la derecha de 3.
    - 40 a la derecha de 22.
    - 45 a la derecha de 40.
    - 13 a la derecha de 8.
    - 20 a la derecha de 15.
    - 30 a la izquierda de 40.
    - 1 a la izquierda de 3.
    - 7 a la izquierda de 8.
    - 34 a la derecha de 30.
    - 48 a la derecha de 45.
    - 53 a la derecha de 48.
    - 9 a la izquierda de 13.
    - 23 a la izquierda de 30.
    - 12 a la derecha de 9.
    - 51 a la izquierda de 48.
    - 4 a la izquierda de 7.
    - 10 a la izquierda de 12.
    -Insertar.

    Ejemplo, en este caso corresponde al último nodo que he insertado (10).

    - Como resultado tenemos una estructura con un total de 20 nodos (incluida la raíz), también se
    puede observar que presenta un nivel altura 8 (h= 8). Árbol binario No perfecto.

    -Búsqueda.
    Al realizar la búsqueda del nodo 10, el camino recorrido dentro de la estructura es el siguiente:
    2.- Utilizando la siguiente imagen desarrolle las actividades señaladas:

    a.-Indique si representa un árbol binario o un árbol convencional. Señale2 argumentos que


    justifiquen su respuesta. (1,5 puntos)
    b.-Confeccione una tabla comparativa entre ambos tipos de Árboles que contenga a lo
    menos 2 elementos a comparar. (1,5 puntos)
    R:
    A.- La estructura corresponde a un árbol binario, y los argumentos son los siguientes:

    1- Un árbol binario corresponde a una estructura de datos recursiva, en donde cada uno sus
    nodos (incluida la raíz) pueda tener como máximo dos hijos (uno izquierdo y otro
    derecho). De ahí radica su nombre “binario”. Cada nodo puede tener cero, uno o dos
    hijos conocidos como subárboles.

    2- Es posible representar un árbol binario usando punteros o referencias las cuales definen la
    secuencia de nodos que contiene (uno para hijo izquierdo y otro para hijo derecho). Es
    primordial identificar el nodo raíz (primer nodo lógico de la estructura), el cual no posee
    padre o antecesor. Este tipo de árbol entonces se divide en tres subconjuntos: Nodo raíz,
    subárbol izquierdo de R y subárbol derecho de R.

    NodoActual

    Subárbol izquierdo Subárbol derecho

    B.- Tabla comparativa entre árbol convencional y árbol binario.

    Árbol convencional Árbol binario


    1 -También conocido como árbol n-arios -Se caracteriza porque cada nodo solo
    corresponde a aquellas estructuras donde el podrá acceder a un máximo de 2 hijos (hijo
    número máximo de hijos que pueda tener izquierdo, hijo derecho).
    cada nodo es de N.
    2 -Al tener cada nodo una cantidad -Por su característica de búsqueda de tipo
    indeterminada de hijos, las operaciones balanceada (divide en 2) esta estructura nos
    sobre este tipo de estructuras serán más permite buscar, insertar y eliminar
    lentas. elementos de forma más rápida. Siendo este
    tipo de árbol el de uso más común.

    3.- Utilizando los nodos presentados en la pregunta 1 explique de qué forma se realiza un
    recorrido preorden. Establecer paso a paso el procedimiento utilizado. (3 puntos)

    R:

    Para realizar el recorrido en pre-orden debemos iniciar en la raíz y posteriormente recorrer cada
    uno de los subárboles de izquierda a derecha.

    En el caso de la estructura de árbol binario de búsqueda (ABB) que he desarrollado el recorrido


    en pre-orden sería el siguiente:

    -Recorrido Pre-orden. (Raíz – Izquierdo – Derecho)


    -Inicia con nodo raíz 22.
    -De 22 visito el siguiente nodo izquierdo 3.
    -De 3 visito el siguiente nodo izquierdo 1.
    - Como 1 apunta a Null, visito nodo derecho de 3 que sería 8.
    -De 8 visito nodo izquierdo 7.
    -De 7 visito nodo izquierdo 4.
    -Como 4 apunta a Null, visito nodo derecho de 8 que sería 13.
    -De 13 visito nodo izquierdo 9.
    -De 9 visito nodo izquierdo 12.
    -De 12 visito nodo izquierdo 10.
    -Como 10 apunta a Null, me dirijo a nodo derecho de 15 que sería 20.
    -Como 20 apunta a Null me dirijo a nodo derecho de 22 (raíz) que sería 40.
    -De 40 visito nodo izquierdo 30.
    -De 30 visito nodo izquierdo 23.
    -Como 23 apunta a Null, me dirijo a nodo derecho de 30 que sería 34.
    -Como 34 apunta a Null, me dirijo a nodo derecho de 40 que sería 45.
    -45 no posee nodo izquierdo, me dirijo a su nodo derecho que sería 48.
    -48 no posee nodo izquierdo, me dirijo a su nodo derecho que sería 53.
    -De 53 visito nodo izquierdo 51.
    - Fin recorrido.

    Post-Orden: 22 – 15 – 3 – 1 – 8 – 7 – 4 – 13 – 9 – 12 – 10 – 20 – 40 – 30 – 23 – 34 – 45- 48 – 53
    – 51.

    Bibliografía
     IACC (2019). Árboles II. Estructura de Datos. Semana 8.
     https://visualgo.net/es/bst
     http://zomwi.blogspot.com/2012/05/convertir-un-arbol-n-ario-binario.html
     https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/

    También podría gustarte