PRESENTACION ARBOLES 2012

Árbol

ÍNDICE DE CONTENIDOS




Concepto de árbol
Terminología básica
Árboles binarios
Árboles binarios
Propiedades
Operaciones del TAD
Recorridos
—In-orden
—Pre-orden
—Post-orden

Concepto de árbol




Estructura JERÁRQUICA no lineal
Relaciones padre-hijo entre nodos
Ejemplos: sistema de ficheros, estructura de un
libro, diagrama de clases JAVA, diagrama
MiEmpresa
organizativo...Producción

Ventas

ES

Europa

Internacional

Asia

Portátiles

América

Sobremesa

I+D

Concepto de árbol


Un árbol se caracteriza por estar formado por
una serie de nodos conectados por una serie de
aristas que verifican que:
hay un único nodo raíz
cada nodo, excepto la raíz, tienen un único
padre
hay un único camino (desde la raíz hasta cada
nodo)

Terminología básica







Raíz: úniconodo sin padre
Nodo interno: tiene al
menos un hijo
Nodo hoja (externo): no
tiene hijos
B
Descendiente directo:
hijo
E
Descendientes: hijo,
nieto...
Subárbol: árbol formado I
por un nodo y sus
descendientes

A

C

F

J

G

K

D

H

subárbol

Terminología básica





Grado de un nodo: número de
descendientes directos
Grado del árbol: mayor grado de sus nodos
Árbol binario: árbol de grado 2
Cadanodo tiene como mucho dos descendientes
directos



Árbol multicamino: árbol de grado mayor
que 2
Cada nodo puede tener n descendientes directos



Lista= árbol degenerado de grado 1

Terminología básica



Profundidad de un nodo: número de
predecesores
Altura del árbol: profundidad máxima de
cualquier nodo
A

B

E

C

F

I

J

G

K

D

H

profundidad(A)=0
profundidad(H)=2
altura=3Terminología básica


Camino: existe un camino
del nodo X al nodo Y, si
existe una sucesión de
nodos que permitan llegar
desde X a Y.

A

B

C

D

camino(A,K)={A,B,F,K}
camino(C,K)={}

E

F

I

J

G

K

H

Árbol binario



Es un árbol de grado 2
Cada nodo tiene de 0 a 2 descendientes
directos: el hijo izquierdo y el derecho
A

B

C

D

E

H

F

I

G

Árbol binario




Aplicación: expresionesaritméticas, árboles
de decisión, búsqueda (ABB)
En algunos casos se exige que el árbol sea
completo = todo nodo interno tiene dos
descendientes.

Árbol binario completo

Árbol binario no completo

Árbol binario


Ejemplo: expresiones aritméticas
nodo interno: operadores
nodos hoja: operandos
( 2(a-1))+3b expresion aritmetica
2*(a-1)+3*b expresion computacional

+



-

2
a

3
1

b

Árbol binario
Ejemplo de aplicación: árboles de decisión
nodo interno: preguntas con respuesta si/no
nodos hoja: decisiones
¿Dónde cenamos?

¿Cómida rápida?
No

Sí

¿Con café?

¿Cara?

Sí

No

Sí

No

Starbucks

McDonalds

Zalacaín

VIPS

Árbol binario: propiedades


Notación



n: número de nodos
e: número de nodos hoja
i: número de nodos
internos
h: altura del árbol

Propiedades
e  2h
h i  2h-1log2(n+1)-1  h  (n-1)/2
2h+1  n  2h+1-1



Si es completo:
eh+1
e=i+1

Árbol binario: operaciones del TAD
Creación de un árbol

crearArbol (nombreArbol)

Comprobación del estado

arbolVacio(nombreArbol)  Booleano

Inserción de nodos

insertar(padre, valorInfo, posicion)

Borrado de nodos

borrar(nombreArbol, valorInfo)

Búsqueda de un nodo

buscar(nombreArbol, dato)  informacion
buscar(nombreArbol,información)referenciaNodo

Recorrido del árbol

recorrer(nombreArbol,tipoRecorrido)

Acceso a los nodos

Modificación de los nodos

info(referenciaNodo)  Informacion
izq(referenciaNodo)  enlace
der(referenciaNodo)  enlace
eshoja(referenciaNodo)  Booleano
asignarInfo(referenciaNodo, valorInformacion)
asignarIzq(referenciaNodo, valorEnlace)
asignarDer(referenciaNodo, valorEnlace

Árbolbinario: recorridos


Hay tres tipos de recorrido en un árbol
binario
in-Orden
pre-Orden
post-Orden

Árbol binario: recorridos


Recorrido IN-ORDEN
cada nodo se visita tras visitar su subárbol
izquierdo y antes de visitar el derecho
(izq, raiz, der)
Ejemplo:
h
in-orden: (i, e, h, a, m)
m

i
e

a

Árbol binario: recorridos


Recorrido PRE-ORDEN
primero se visita cada nodo, luego su subárbol...