Árboles estructuras de datos mc beatriz beltrán martínez primavera 2015

ÁrbolesEstructuras de Datos

MC Beatriz Beltrán MartínezPrimavera 2015

Introducción

• Aparecen estructuras de tipo árbol en:• Sistemas Operativos: Sistema de ficheros (Árbol de

directorios).• Compiladores, procesadores de textos, algoritmos de

búsqueda.• Elementos:

• Nodos.• Conexiones (dirigidas) entre pares de nodos.• Un nodo particular: Raíz.• Cada nodo (excepto raíz) está conectado al menos

con otro (padre). Relación padre-hijo.2

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Conceptos

• Un único camino conduce de la raíz a cada nodo.• Longitud del camino: Número de conexiones a

atravesar.• Nodos sin hijos: Hojas (leaves).• Árbol con N nodos N-1 conexiones entre nodos.• Profundidad de un nodo:

• Longitud del camino raíz nodo.• Altura de un nodo:

• Longitud del camino desde el nodo a su hoja más profunda.

• Hermanos: Nodos con el mismo padre (siblings).3

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Conceptos

• El grado de un nodo es el número de flechas que salen de ese nodo.

• El grado de un árbol es el mayor de los grados que puede hallarse en el árbol.

• Un camino de un nodo n1 a otro nk, se define como la secuencia de nodos n1, n2, ... nk tal que ni es padre de ni+1

para 1 i < k.• Longitud del camino entre 2 nodos, es el número de

arcos que hay entre ellos.

4

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Conceptos

• Relación antepasado (u) / descendiente (v):• Si hay camino de u a v.

• Tamaño de un nodo:• Número de descendientes (incluyendo al nodo).

• Árbol (definición recursiva):• o es vacío,• o consiste en una raíz y cero o más (sub)árboles no

vacíos A1..Ak conectados a la raíz.

5

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Implementación

1. Cada nodo contiene:• Referencias a todos sus hijos.• Datos almacenados en el nodo.• Problema: Número de hijos desconocido.

2. Cada nodo:• Lista con sus hijos.• Referencia a los datos contenidos.• Referencia a su nodo hermano.• Representación "first child / next sibling“.

6

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Implementación

7

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

sigHermanoprimerHijo

null

nullnull

nullnull null null null

nullnull

nodoRaiz

Árbol N-ario

• Ningún nodo puede tener más de N hijos.• El más utilizado: Binario, 2 hijos (left, right).• Definición recursiva (Árbol binario):

• ... o es vacío.• ... o tiene raíz, árbol derecho, árbol izquierdo.

• Implementación:• Conocido el número de hijos. 2 referencias.

8

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Árboles Binarios

• Árbol binario lleno (full binary tree).• Todas las hojas tiene la misma profundidad.• El resto de nodos (no terminales) tienen 2 hijos.

• Árbol binario completo (complete binary tree).• Cada nivel (excepto el más profundo) debe contener

todos sus posibles nodos.• En el nivel más profundo, los nodos están lo más a la

izquierda que sea posible.

9

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Expresiones

• Un nodo terminal representa un operando.• El resto de los nodos representan operadores (binarios).

10

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Evaluación de la expresión:Evaluación de los subárboles (recursivamente).Aplicación del operador a los valores obtenidos.

6 + ((7 - 3) * 5)+

6 *

5-

37

Recursividad• El tipo árbol se define recursivamente.• Muchas rutinas para manejo de árboles se implementan

fácilmente de forma recursiva.public class NodoBinario{ Object dato; NodoBinario left; NodoBinario right; public NodoBinario (Object elemento) { dato = elemento; left = null; right = null; } // Métodos...} 11

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

dato

rightleft

Recorridos

• Recorrido:• Acceso a todos los nodos de un árbol• Ej: Para realizar una operación en cada nodo

• Fácil implementación mediante recursividad.• Tipos de recorrido:

• Según el orden en que se "visitan" los nodos.• Recorrido preorder.• Recorridos postorder.• Recorridos inorder.

12

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

Recorridos

• Recorrido preorden:1. Nodo raíz2. Subárbol left en preorden3. Subárbol right en preorden

13

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

// en la clase NodoBinariopublic void mostrarPreorden(){ System.out.println(dato); if (left != null) left.mostrarPreorden(); if (right != null) right.mostrarPreorden();}

1Preorden

2 3

64

5 7

Recorridos

• Recorrido inorden:1. Subárbol left en inorden2. Nodo raíz3. Subárbol right en inorden

14

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

2Inorden

1 5

73

4 6

// en la clase NodoBinariopublic void mostrarInorden(){ if (left != null) left.mostrarInorden(); System.out.println(dato); if (right != null) right.mostrarInorden();}

Recorridos

• Recorrido postorden:1. Subárbol left en postorden2. Subárbol right en postorden3. Nodo raíz

15

MC

Bea

triz

Bel

trán

Mar

tínez

FC

C-B

UA

P

Prim

aver

a 20

15

7Postorden

1 6

53

2 4

// en la clase NodoBinariopublic void mostrarPostorden(){ if (left != null) left.mostrarPostorden(); if (right != null) right.mostrarPostorden(); System.out.println(dato);}