Tema 6 - Árboles

El TAD Árbol Binario, definiciones, especificación informal, implementación y descripción gráfica. Operaciones explicadas de forma gráfica e implementadas. Recorridos en profundidad (preorden, inorden y posorden) y recorrido en anchura.

¿Qué es un árbol?

---
title: Esto es un Árbol
---
flowchart TB
    A(((_A_))) --> B((_B_)) & C((_C_)) & F((_F_))
    B --> G((_G_)) & H((_H_))

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.

Árbol Lleno:

flowchart TB
    A(((_A_))) --> B((_B_)) & C((_C_))
    B --> D((_D_)) & E((_E_))
    C --> F((_F_)) & G((_G_))

Árbol Completo:

flowchart TB
    A(((_A_))) --> B((_B_)) & C((_C_))
    B --> D((_D_)) & E((_E_))
    C --> F((_F_)) & NULL(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 caso: á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.

---
title: TAD Árbol Binario
---
flowchart TB
    TREE[ÁRBOL] --> A[[A]] --> B[[B]] & C[[C]]
    B --> D[[D]] & E[NULL]
    D --> H[NULL] & I[NULL]
    C --> F[NULL] & G[NULL]

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

createEmptyTree → Tree

createEmptyTree \rightarrow Tree

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

flowchart LR
    TREE(ÁRBOL) -.-> NULL[[NULL]]

Mostrar implementación

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

void createEmptyTree(tBinTree *T){

    *T = TNULL;

}

BuildTree(Tree, Item, Tree) → Tree, bool

BuildTree (Tree, Item, Tree) \rightarrow Tree, bool

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.

flowchart TB
    TREE1(ÁRBOL1) -.-> A[[A]] --> B[[B]] & C[[C]]
    ITEM
    TREE2(ÁRBOL2) -.-> 1[[1]] --> 2[[2]] & 3[[3]]

flowchart TB
    TREE1(ÁRBOL1) -.-> A[[A]] --> B[[B]] & C[[C]]
    TREE3(ÁRBOL) -.-> ITEM[[ITEM]]
    TREE2(ÁRBOL2) -.-> 1[[1]] --> 2[[2]] & 3[[3]]

flowchart TB
    TREE1(ÁRBOL1) -.-> A[[A]] --> B[[B]] & C[[C]]
    TREE3(ÁRBOL) -.-> ITEM[[ITEM]] --> A & 1
    TREE2(ÁRBOL2) -.-> 1[[1]] --> 2[[2]] & 3[[3]]

Mostrar implementación

// 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

leftChild(Tree) → Tree

leftChild(Tree) \rightarrow Tree

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

flowchart TB
    A[[A]] --> B[[B]] & C[[C]]
    LEFT(leftChild) -.-> B

Mostrar implementación

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

tBinTree LeftChild(tBinTree T){

    return T->left;

}

rightChild(Tree) → Tree

rightChild(Tree) \rightarrow Tree

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

flowchart TB
    A[[A]] --> B[[B]] & C[[C]]
    RIGHT(rightChild) -.-> C

Mostrar implementación

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

tBinTree RightChild(tBinTree T){

    return T->right;ç

}

root(Tree) → Item

root(Tree) \rightarrow Item

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

flowchart TB
    TREE2(ROOT = B) -.-> B
    TREE1(ROOT = A) -.-> A[[A]] --> B[[B]] & C[[C]]
    TREE3(ROOT = C) -.-> C

Mostrar implementación

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

tItemT Root(tBinTree T){

    return  T->data;

}

isEmptyTree(Tree) → bool

isEmptyTree(Tree) \rightarrow bool

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

flowchart TB
    A[[A]] --> B[[B]] & C[[C]]
    B --> NULLB1(NULL) & NULLB2(NULL)
    EMPTY2(isEmptyTree = false) -.-> C --> NULLC1(NULL) & NULLC2(NULL)
    EMPTY1(isEmptyTree = true) -.-> NULLC2

Mostrar implementación

// SPDX-FileCopyrightText: 2023 Fernando Álvarez
//
// SPDX-License-Identifier: GPL-3.0-only

bool isEmptyTree(tBinTree T){

    return (T==TNULL);

}

Recorridos de Árboles

---
title: Árbol de ejemplo
---
flowchart TB
    A((_A_)) --> B((_B_)) & C((_C_))
    B --> D((_D_)) & E((_E_))
    C --> G((_G_)) & H((_H_))
    E --> F((_F_)) & NULL(NULL)

Recorridos en profundidad

Vídeo explicativo de los recorridos en profundidad.

Preorden (R | ID)

(R) Raíz
(I) Izquierdo
(D) Derecho

flowchart TB
    RECORRIDO[A, B, D, E, F, C, G, H]
    A((_A_)) --> B((_B_)) & C((_C_))
    A -. " (R) " .-> A
    B --> D((_D_)) & E((_E_))
    D --> NULL3(NULL) & NULL4(NULL)
    C --> G((_G_)) & H((_H_))
    E --> F((_F_)) & NULL(NULL)
    A -. " (I) " .-> B -. " (R) " .-> B -. " (I) " .-> D
    D -. " (R) " .-> D -. " (I) " .-> NULL3 -.-> D -. " (D) " .-> NULL4
    NULL4 -.-> D -.-> B -. " (D) " .-> E -. " (R) " .-> E -. " etc " .-> F

Inorden (I | R | D)

(I) Izquierdo
(R) Raíz
(D) Derecho

flowchart TB
    RECORRIDO[D, B, F, E, A, G, C, H]
    A((_A_)) --> B((_B_)) & C((_C_))
    B --> D((_D_)) & E((_E_))
    D --> NULL3(NULL) & NULL4(NULL)
    C --> G((_G_)) & H((_H_))
    E --> F((_F_)) & NULL(NULL)
    A -. " (I) " .-> B -. " (I) " .-> D -. " (R) " .-> D
    D -. " (I) " .-> NULL3 -.-> D -.-> B -. " (R) " .-> B
    B -. " (D) " .-> E -. " etc " .-> F

Posorden (ID | R)

(I) Izquierdo
(D) Derecho
(R) Raíz

flowchart TB
    RECORRIDO[D, F, E, B, G, H, C, A]
    A((_A_)) --> B((_B_)) & C((_C_))
    B --> D((_D_)) & E((_E_))
    D --> NULL3(NULL) & NULL4(NULL)
    C --> G((_G_)) & H((_H_))
    E --> F((_F_)) & NULL(NULL)
    A -. " (I) " .-> B -. " (I) " .-> D -. " (I) " .-> NULL3
    NULL3 -.-> D -. " (D) " .-> NULL4 -.-> D -. " (R) " .-> D
    D -.-> B -. " (D) " .-> E -. " etc " .-> F

Recorrido en anchura

flowchart TB
    RECORRIDO[A, B, C, D, E, F, G, H, F]
    A((_A_)) --> B((_B_)) & C((_C_))
    B --> D((_D_)) & E((_E_))
    C --> G((_G_)) & H((_H_))
    E --> F((_F_)) & NULL(NULL)

    subgraph 1
        A
    end
    subgraph 2
        B & C
    end
    subgraph 3
        D & E & G & H
    end
    subgraph 4
        F & NULL
    end