Pro2324 Help

Tema 6 - Árboles

Pásame El Código

Visita nuestra nueva página web con contenidos actualizados y mucho más.

Estos apuntes también están en: Pásame el Código

    ¿Que es un árbol?

    A

    B

    C

    F

    G

    H

    Esto es un Árbol

    Definido por:

    • Una raíz: A, padre de B, C y F.

    • G hermanos H, hijos de B y descendientes de A.

    • Altura del árbol: 3

    • Grado del árbol: 3 (Nº de hijos máximo, alcanzado por A)

    Para trabajar con Árboles Binarios es importante tener claro el concepto de árbol lleno y árbol completo.

    Árbol Lleno

    Árbol Completo

    Todas sus hojas están al mismo nivel h y todos los nodos anteriores tienen el número máximo de hijos (en un árbol binario, 2).

    Todas sus hojas llenas hasta h-1 y todos los nodos del nivel h están lo más a la izquierda posible.

    A

    B

    C

    D

    E

    F

    G

    A

    B

    C

    D

    E

    F

    NULL

    TAD Árbol Binario

    Un árbol binario es un conjunto cero o más de elementos del mismo tipo llamados nodos.

    • O bien 0 nodos, en cuyo casa: árbol vacío

    • O bien existe un elemento distinguido llamado raíz, y el resto de los nodos se distribuyen en dos subconjuntos, y a su vez cada nodo tiene una serie de hasta dos hijos los cuales solo pueden tener hasta dos hijos. Formando así los subconjuntos siguientes.

    ÁRBOL

    A

    B

    C

    D

    NULL

    NULL

    NULL

    NULL

    NULL

    TAD Árbol Binario

    Operaciones

    Siguiendo los pasos para la especificación de un TAD, definimos las operaciones del mismo clasificándolas en: constructoras, generadoras, modificadoras, observadoras y destructoras.

    Generadoras

    • Objetivo: Crea un árbol vacío
      Salida: Un árbol vacía
      PosCondición: El árbol sin datos

      ÁRBOL

      NULL

      // SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only void createEmptyTree(tBinTree *T){ *T = TNULL; }

    • Objetivo: Crea un árbol con cierta información en la raíz y como hijos los árboles que se reciben en las entradas.
      Entrada:
      - Tree(1): Árbol que constituirá el hijo izquierdo.
      - Item: Contenido del elemento raíz.
      - Tree(2): Árbol que constituirá el hijo derecho.
      Salida: Tree: Nuevo árbol construido y verdadero si se ha podido construir, falso en caso contrario.

      1

      2

      3

      ÁRBOL1

      A

      B

      C

      ITEM

      ÁRBOL2

      1

      2

      3

      ÁRBOL1

      A

      B

      C

      ÁRBOL

      ITEM

      ÁRBOL2

      1

      2

      3

      ÁRBOL1

      A

      B

      C

      ÁRBOL

      ITEM

      ÁRBOL2

      // SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only bool BuildTree(tBinTree LT,tItemT itemT,tBinTree RT,tBinTree *T){ if(createNode(T)){ (*T)->data=itemT; (*T)->left=LT; (*T)->right=RT; return true; } else return false; }

    Observadoras

    • Objetivo: Devuelve el árbol que constituye el hijo izquierdo del árbol
      Entrada: Tree: Árbol a manipular
      Salida: Tree: Árbol que constituye el hijo izquierdo o nulo del árbol
      Precondición: El árbol no está vacío

      A

      B

      C

      leftChild

      // SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only tBinTree LeftChild(tBinTree T){ return T->left; }

    • Objetivo: Devuelve el árbol que constituye el hijo derecho del árbol
      Entrada: Tree: Árbol a manipular
      Salida: Tree: Árbol que constituye el hijo derecho o nulo del árbol
      Precondición: El árbol no está vacío

      A

      B

      C

      rightChild

      // SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only tBinTree RightChild(tBinTree T){ return T->right;ç }

    • Objetivo: Devuelve el dato de la raíz del árbol
      Entrada: Tree: Árbol a manipular
      Salida: Item: Contenido del elemento de la raíz
      PreCondición: El árbol no está vacío

      ROOT = B

      B

      ROOT = A

      A

      C

      ROOT = C

      // SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only tItemT Root(tBinTree T){ return T->data; }

    • Objetivo: Determina si el árbol está vacío
      Entrada: Tree: Árbol a manipular
      Salida: Verdadero si el árbol está vacía, falso en caso contrario

      A

      B

      C

      NULL

      NULL

      isEmptyTree = false

      NULL

      NULL

      isEmptyTree = true

      // SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only bool isEmptyTree(tBinTree T){ return (T==TNULL); }

    Recorridos de Árboles

    A

    B

    C

    D

    E

    G

    H

    F

    NULL

    Árbol de ejemplo

    Recorridos en profundidad

    Vídeo explicativo de los recorridos en profundidad.

    Preorden (R | ID)

    • (R) Raíz

    • (I) Izquierdo

    • (D) Derecho

    (R)

    (I)

    (R)

    (I)

    (R)

    (I)

    (D)

    (D)

    (R)

    etc

    A, B, D, E, F, C, G, H

    A

    B

    C

    D

    E

    NULL

    NULL

    G

    H

    F

    NULL

    Inorden (I | R | D)

    • (I) Izquierdo

    • (R) Raíz

    • (D) Derecho

    (I)

    (I)

    (R)

    (I)

    (R)

    (D)

    etc

    D, B, F, E, A, G, C, H

    A

    B

    C

    D

    E

    NULL

    NULL

    G

    H

    F

    NULL

    Posorden (ID | R)

    • (I) Izquierdo

    • (D) Derecho

    • (R) Raíz

    (I)

    (I)

    (I)

    (D)

    (R)

    (D)

    etc

    D, F, E, B, G, H, C, A

    A

    B

    C

    D

    E

    NULL

    NULL

    G

    H

    F

    NULL

    Recorrido en anchura

    1

    2

    3

    4

    A, B, C, D, E, F, G, H, F

    A

    B

    C

    D

    E

    G

    H

    F

    NULL

    Last modified: 16 marzo 2025
    Tema 4 y 5 - Colas y PilasTema 7 y 8 - Árboles Binarios de Búsqueda ABB y Equilibrados AVL