Fys ro

Clase 26

Introducción a los árboles

Árboles
• Árbol es el nombre que se le da a un grupo versátil de estructuras de datos. • Se pueden utilizar para implementar un número de interfaces abstractas, incluida la interfaz List, pero las aplicaciones en las que resultan más útiles emplean estructuras de ramas de árboles para representar alguna propiedad de los elementos de los datos o paraoptimizar ciertos métodos. • Por ejemplo, los árboles de juegos Minimax se suelen utilizar en programas de juegos para representar la forma en que las posiciones de la clasificación se multiplican a partir de una situación original.
2

1

Terminología del árbol
raíz Padre de B
Antecesores de D

A

B

Descendentes de o el subárbol ligado a C

C

D

E
Hijos de B

F

G

Hhojas
3

Árboles, nodos y raíces
• Un árbol consta de nodos conectados. • Cada árbol (salvo un árbol vacío degenerado) cuenta con un nodo distinguido llamado raíz. • No puede haber rutas circulares en las conexiones de un árbol, de tal forma que sólo puede existir una ruta única desde cada nodo hasta la raíz.
4

2

Nodos hijos y padres
• Todos los nodos conectados a un nodo concreto sonhijos o bien el padre de dicho nodo. • Si el nodo conectado se encuentra en la única ruta a la raíz, dicho nodo recibe el nombre de padre. Todos los nodos, salvo la raíz, tienen un único padre. • El resto de nodos conectados a un nodo concreto son los hijos del nodo.
5

Antecesores, descendientes y subárboles
• Los nodos que se encuentran en la ruta que va desde un nodo a la raíz reciben elnombre de antecesores del nodo e incluyen a su padre, al padre de su padre, etc., hasta llegar a la raíz. • El conjunto de nodos que incluyen a los hijos del nodo, a los hijos del hijo, etc., reciben el nombre de descendientes del nodo. • Un nodo y sus descendientes forman un subárbol enraizado a dicho nodo. • Un nodo sin hijos recibe el nombre de hoja.
6

3

Árbol binario
• Un tipo de árbolhabitual y de gran utilidad es el llamado árbol binario, que permite que un nodo tenga, al menos, dos hijos. • A continuación se incluye una definición formal del árbol binario que hace hincapié en el carácter recursivo del árbol:
Un árbol binario es un árbol vacío, o bien un nodo raíz con subárboles formados por árboles binarios a la derecha y a la izquierda.
7

Ejemplos de árboles binarios
3.. 1
raíz A B C

2.
raíz raíz B D

E F
8

4

Recorrido del árbol
• Enumerar todos los elementos de un árbol es más complicado que enumerar todos los elementos de una lista enlazada y, además, hay varias formas de hacerlo. • Decimos que la lista de los nodos de un árbol se puede recorrer si enumera cada nodo del árbol exactamente una vez. • Las implementaciones de los árboles suelenconstar de un iterador que enumera los elementos del árbol siguiendo una secuencia predecible.
9

Preorder, Inorder, Postorder
Los tres métodos más comunes para recorrer un árbol se pueden describir, de forma recursiva, del siguiente modo: • preorder: raíz, subárbol izquierdo, subárbol derecho • inorder: subárbol izquierdo, raíz, subárbol derecho • postorder: subárbol izquierdo, subárbol derecho,raíz
10

5

Recorridos
• • • Preorder: A B D E C F H I G Inorder: DBEAHFICG Postorder: D E B H I F G C A
A B C

D

E

F

G

H I

11

Ejercicio de recorrido de árbol
• Descargue TreeTraversal.jar y TreeTraversal.bat del sitio web de clase en el mismo directorio. Puede encontrar los enlaces en la página del material de clase. • Haga doble clic en TreeTraversal.bat paraejecutarlo. • Utilice los botones inferiores para analizar la terminología del árbol. • Utilice los botones superiores para analizar los tres recorridos típicos del árbol: inorder, preorder y postorder.
12

6

Árboles binarios de búsqueda
• Considere un árbol binario con nodos que contienen un entero llamado value que representa el valor del nodo. Haremos que este árbol asuma la propiedad de...