PDF de programación - Árboles - Programación de sistemas

Programación de sistemas



Árboles

Julio Villena Román

<[email protected]>



MATERIALES CREADOS EN EL TRABAJO DE DIFERENTES AUTORES:

Carlos Delgado Kloos, M.Carmen Fernández Panadero,

Raquel M.Crespo García, Carlos Alario Hoyos

1

Contenidos

 Concepto de árbol
 Terminología
 Implementación
 Casos especiales

 Árboles binarios de búsqueda
 Montículos (heaps)

2

Cita

“The structure of concepts is formally


called a hierarchy and since ancient times has
been a basic structure for all Western
knowledge. Kingdoms, empires, churches,
armies have all been structured into
hierarchies. Tables of contents of reference
material are so structured, mechanical
assemblies, computer software, all scientific
and technical knowledge is so structured...”

Robert M. Pirsig:
Zen and the Art of Motorcycle Maintenance

3

Concepto de árbol

Un árbol es una estructura

de datos no lineal que

almacena los elementos

jerárquicamente



(generalización de las listas)

4

Ejemplos

1. Clasificación de la información en una

enciclopedia



5

Ejemplos

2. Sistema de ficheros



6

Ejemplos

3. Estructura organizativa de una empresa

4. Estructura de rangos del ejército

5. Estructura de un libro

…



7

Definición no recursiva

• Un árbol consiste en un conjunto de nodos

y un conjunto de aristas, de forma que:
o Se distingue un nodo llamado raíz

o A cada nodo h (hijo), excepto la raíz, le llega

una arista de otro nodo p (padre)

o Para cada nodo hay un camino (secuencia de

aristas) único desde la raíz

o Los nodos que no tienen hijos se denominan

hojas



8

Definición no recursiva



9

Definición recursiva

• Un árbol es:

o Vacío

o Un nodo y cero o más árboles conectados

al nodo mediante una arista



* A los árboles que se conectan al nodo raíz los denominaremos

también “subárboles”

10

Definición recursiva



11

Definición recursiva



12

Definición recursiva



13

Definición recursiva



14

Definición recursiva



15

Terminología

• Un nodo es externo, si no tiene hijos (es hoja)

o Según la definición recursiva: si todos los subárboles

conectados a ese nodo están vacíos

• Un nodo es interno, si tiene uno o más hijos

o Según la definición recursiva: si alguno de los subárboles

conectados a ese nodo no está vacío

• Un nodo es ascendiente de otro, si es padre suyo

o ascendiente de su padre

• Un nodo es descendiente de otro, si este último

es ascendiente del primero
o Los descendientes de un nodo forman un subárbol en el

que ese nodo hace de raíz



16

Terminología

• Un camino de un nodo a otro, es una secuencia de

aristas consecutivas que llevan del primero al
segundo

o La longitud del camino es el número de aristas

• La profundidad de un nodo es la longitud del

camino de la raíz a ese nodo

• La altura de un árbol es el valor de la

profundidad del nodo más profundo

• El tamaño de un árbol es el número de nodos

que contiene



17

Ejemplo



Nodo Altura Profundidad Tamaño



a

b

c

d

e

f

g

2

1

0

0

0

0

0

0

1

1

1

1

2

2

7

3

1

1

1

1

1

Int./Ext.
Interno

Interno

Externo

Externo

Externo

Externo

Externo

18

Ejercicio 1

• Completa la tabla para el siguiente árbol

Nodo Altura Profundidad Tamaño

a

b

c

d

e

f

g

h

i

j

k

3

1

0

1

2

0

0

0

0

1

0

0

1

1

1

1

2

2

2

2

2

3

11

3

1

2

4

1

1

1

1

2

1

Int./Ext.
Interno

Interno

Externo

Interno

Interno

Externo

Externo

Externo

Externo

Interno

Externo

19

Terminología: Árbol ordenado

• Un árbol es ordenado, si para cada nodo
existe un orden lineal para todos sus hijos



20

Terminología: Árbol binario

• Un árbol binario es un árbol ordenado en el

que cada nodo tiene 2 árboles (izquierdo y
derecho).
o Árbol binario según la definición recursiva de árbol

o

Los árboles izquierdo y/o derecho pueden estar vacíos



* En general, suponemos árboles binarios para simplificar

la implementación de los árboles



21

La interfaz BTree

public interface BTree<E> {

static final int LEFT = 0;
static final int RIGHT = 1;

boolean isEmpty();
E getInfo() throws BTreeException;
BTree<E> getLeft() throws BTreeException;
BTree<E> getRight() throws BTreeException;

void insert(BTree<E> tree, int side) throws BTreeException;
BTree<E> extract(int side) throws BTreeException;

String toStringPreOrder();
String toStringInOrder();
String toStringPostOrder();
String toString(); // preorder

int size();
int height();

boolean equals(BTree<E> tree);
boolean find(BTree<E> tree);
}


22

Una interfaz varias implementaciones

• Implementación basada en arrays



 Subárbol izquierdo

 Posición nodo raíz * 2

 Subárbol derecho

 Posición nodo raíz * 2 +1

23

Una interfaz varias implementaciones

•

Implementación basada en enlaces





Linked Binary Node (LBNode)
Linked Binary Tree (LBTree)

 Cada árbol (LBTree) tiene un nodo raíz (atributo LBNode)
 Cada nodo raíz LBNode apunta a dos árboles (atributos LBTree), los

cuales pueden estar vacíos (null)



24

La clase LBNode

public class LBNode<E> {

private E info;
private BTree<E> left;
private BTree<E> right;

public LBNode(E info, BTree<E> left, BTree<E> right) {…}
public E getInfo() {…}
public void setInfo(E info) {…}
public BTree<E> getLeft() {…}
public void setLeft(BTree<E> left) {…}
public BTree<E> getRight() {…}
public void setRight(BTree<E> right){…}
}

25

Ejercicio 2

• Completa la implementación de

la clase LBNode.

26

La clase LBTree


public class LBTree<E> implements BTree<E> {

private LBNode<E> root;

public LBTree() {
root = null;
}

public LBTree(E info) {
root = new LBNode<E>(info, new LBTree<E>(), new LBTree<E>());
}

public boolean isEmpty() {
return (root == null);
}
…

27

La clase LBTree

…
public E getInfo() throws BTreeException {
if (isEmpty()) {
throw new BTreeException("empty trees do not have info");
}
return root.getInfo();
}

public BTree<E> getLeft() throws BTreeException {
if (isEmpty()) {
throw new BTreeException("empty trees do not have a left child");
}
return root.getLeft();
}

public BTree<E> getRight() throws BTreeException {
if (isEmpty()) {
throw new BTreeException("empty trees do not have a right child");
}
return root.getRight();
}
…

28

Algoritmos básicos

• Tamaño: size()
• Altura: height()
• Recorridos

o Pre-orden: toStringPreOrder()
o In-orden: toStringInOrder()
o Post-orden: toStringPostOrder()



29

La clase LBTree: size()


public int size() {
if (isEmpty()) {
return 0;
} else {
return 1 + root.getLeft().size()
+ root.getRight().size();
}
}

30

La clase LBTree: height()


public int height() {
if (isEmpty()) {
return -1;
} else {
int leftHeight = root.getLeft().height();
int rightHeight = root.getRight().height();
if (leftHeight > rightHeight) {
return 1 + leftHeight;
} else {
return 1 + rightHeight;
}
}
}

1+Math.max(leftHeight,
rightHeight);

31

Recorrido de Euler

32

Recorrido Pre-orden

 Primero el nodo raíz
 Después sus hijos
(recursivamente)

33

La clase LBTree:

toStringPreOrder()

public String toStringPreOrder() {
if (isEmpty()) {
return "";
} else {
return root.getInfo().toString() + " " +
root.getLeft().toStringPreOrder() +
root.getRight().toStringPreOrder();
}
}

34

Recorrido Post-orden

 Primero los hijos
(recursivamente)

 Después el nodo raíz


35

La clase LBTree:

toStringPostOrder()

public String toStringPostOrder() {
if (isEmpty()) {
return "";
} else {
return root.getLeft().toStringPostOrder() +
root.getRight().toStringPostOrder() +
root.getInfo().toString() + " ";
}
}

36

Recorrido In-orden (simétrico)

 Primero el hijo izquierdo

(recursivamente)

 Después el nodo raíz
 Después el hijo derecho

(recursivamente)



37

La clase LBTree:

toStringInOrder()

public String toStringInOrder() {
if (isEmpty()) {
return "";
} else {
return root.getLeft().toStringInOrder() +
root.getInfo().toString() + " " +
root.getRight().toStringInOrder();
}
}

38

Ejercicio 3

• Dado el siguiente árbol binario, indica qué
recorrido (pre-orden, in-orden, post-orden)

produce el resultado (A+B)*(C-D).

39

Diferente notación matemática

Infix

A+B

Prefix

Postfix

+AB

AB+

A+B–C

–+ABC

AB+C–

(A+B)*(C–D)

*+AB–CD

AB+CD–*

40

Actividad

Expresiones matemáticas como árboles:
http://www.cs.jhu.edu/~goodrich/dsa/05trees/Demo1/

41

Programación de sistemas



Árboles (II)



Julio Villena Román

<[email protected]>



MATERIALES BASADOS EN EL TRABAJO DE DIFERENTES AUTORES:

Carlos Delgado Kloos, M.Carmen Fernández Panadero,

Raquel M.Crespo García, Carlos Alario Hoyos

42

Contenidos

 Concepto de árbol
 Terminología
 Implementación
 Casos especiales

 Árboles binarios de búsqueda
 Montículos (heaps)

43

Notación

• Hasta ahora:

o Un nodo, tres atributos: información almacenada,

subárbol izquierdo