Tema 6 - Árboles

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?

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.

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.

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
// 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.
// 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
// 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
// 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
// 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
// SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only bool isEmptyTree(tBinTree T){ return (T==TNULL); }

Recorridos de Árboles

Recorridos en profundidad

Vídeo explicativo de los recorridos en profundidad.

Preorden (R | ID)

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

Inorden (I | R | D)

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

Posorden (ID | R)

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

Recorrido en anchura

Last modified: 02 November 2024