Download Tema 7: Árbol Binario Estructuras de datos Contenido Applet del

1
2
Estructuras de datos
Nivel de
Abstracción
Tema 7: Árbol Binario
Javier Miranda
Estructura de datos
Alto
Pila, Cola, Árbol, Hash, Grafo
Bajo
Array, Lista Enlazada, Árbol
Ordenación
18-feb-04
(C) Javier Miranda
18-feb-04
(C) Javier Miranda
3
4
Contenido
Applet del
árbol binario
• Terminología
• Árbol binario
• Recorridos:
Run
– Pre-order
– In-order
– Post-order
• Resumen
18-feb-04
(C) Javier Miranda
18-feb-04
(C) Javier Miranda
5
6
Recorridos de un árbol
Terminología
•
•
•
•
•
•
•
18-feb-04
• Pre-order: Primero el padre y después sus
Camino
Raíz
Padre
Hijo
Hoja
Subárbol
Niveles
hijos.
• In-order: Primero el hijo izquierdo, después el
padre y después el hijo derecho.
• Post-order: Primero los hijos y después el
padre.
(C) Javier Miranda
18-feb-04
(C) Javier Miranda
1
7
8
Borrado de un nodo del árbol
Interfaz de árbol
• Insertar (valor)
• Caso 1: No tiene hijos
Error: Lleno
• Existe (valor)
• Caso 2: Tiene un hijo.
• Borrar (valor)
• Caso 3: Tiene dos hijos
Error: No encontrado
• Recorrer en preorder
• Recorrer en inorder
• Recorrer en postorder
18-feb-04
(C) Javier Miranda
18-feb-04
(C) Javier Miranda
9
10
Resumen
AVISO IMPORTANTE
La tercera práctica debe contener
la implementación de un paquete
que gestione un árbol binario con
todas las operaciones de la interfaz
anterior
18-feb-04
(C) Javier Miranda
• La raíz del árbol es el que no tiene padre.
• Todos los nodos con claves menores se
colocan a la izquierda y los mayores a la
derecha.
• Búsqueda, inserción y borrado de O(log N)
• Recorrer un árbol significa visitar todos sus
nodos. Las tres formas básicas son:
preorder, inorder y postorder.
18-feb-04
(C) Javier Miranda
2