Tema 6 - Árboles
¿Que es un árbol?
Definido por:
Una raíz:
A
, padre deB
,C
yF
.G
hermanosH
, hijos deB
y descendientes deA
.Altura del árbol:
3
Grado del árbol:
3
(Nº de hijos máximo, alcanzado porA
)
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 | Todas sus hojas llenas hasta |
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