Digrafo

...

N. Nivel del nodo E: 0 Nivel

O. Grado del nodo E: 3

P. Peso del nodo D2: 3

Q. Grado del nodo T1: 0

R. Peso del nodo T2: 0

S. Peso del nodo S2: 6

T. Profundidad del nodo T2: 3

U. Tipo de árbol: General

Tipos de árboles binarios

Desde su concepción general, los árboles binarios pueden ser:

- Distinto

- Similares

- Equivalentes

Árboles binarios distintos

Dos árboles binarios son distintos cuando sus estructuras son diferentes.

Ejemplo:

[pic 4]

Árboles binarios similares

Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos difiere entre sí.

Ejemplo:

[pic 5]

Árboles binarios equivalentes

Los árboles binarios equivalentes se definen como aquellos que son similares y además los nodos contienen la misma información.

Ejemplo:

[pic 6]

TIPOS DE ARBOL

Árbol Binario: Es un conjunto finito de elementos o nodos que está dividido en 3 subconjuntos separados. El primer subconjunto contiene un elemento único llamado raíz del árbol o vértice principal del árbol. Los dos otros subconjuntos se los conoce como subárboles izquierdo y derecho del árbol original.

[pic 7]

Árbol Estrictamente Binario: Es un árbol en el cual todo nodo que no es hoja tiene asociados subárboles izquierdo y derecho no vacío. En este tipo de árbol el número de nodos es 2n-1, donde n es la cantidad de hojas que tiene el árbol.

[pic 8]

Árbol Binario Completo: Es aquel en que todos los nodos no terminales tienen sus 2 ramificaciones y sus hojas están en el último nivel.

[pic 9]FUNCIONES PARA EL MANEJO DE ÁRBOLES BINARIO

Creación de árboles El teorema consiste en:

- Los valores menores o iguales se guardan a la izquierda.

- Los valores mayores se guardan a la derecha.

Ejemplos:

1.Realizar el árbol correspondiente a partir de los siguientes nodos: 20, 10, 30 15, 40, 5, 50, 7, 4, 16, 25, 52, 38, 49, 3, 3.

[pic 10]

En función de ello, determinar:

- Altura del árbol: 5

- Peso del nodo 40: 4

- Raíz del árbol: 20

- Hijos del 50: 2

- Hojas del árbol

- Altura del nodo 40: 2

2.Crear un árbol binario a partir del siguiente conjunto de datos: 20, 10, 30, 15, 40, 5, 4, 50, 5.

[pic 11]

Recorridos de Arboles

Es el proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol.

Existen distintos métodos útiles en que se puede recorrer sistemáticamente todos los nodos de un árbol. Los tres recorridos más utilizados son:

- Pre-orden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en pre-orden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

- Visite la raíz

- Atraviese el sub-árbol izquierdo

- Atraviese el sub-árbol derecho

- In-orden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en in-orden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

- Atraviese el sub-árbol izquierdo

- Visite la raíz

- Atraviese el sub-árbol derecho

- Post-orden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en post-orden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

- Atraviese el sub-árbol izquierdo

- Atraviese el sub-árbol derecho

- Visite la raíz

[pic 12]

Pre-orden(R-SI-SD)

10, 5, 1, 4, 6, 7, 15, 17, 50

In-orden (SI-R-SD)

1, 4, 5, 6, 7, 10, 15, 16, 17

Post-orden(SI-SD-R)

1, 4, 6, 7, 5, 16, 17, 15, 10

Miscelánea de Ejercicios

1. Dado el siguiente conjunto de datos, crear el árbol binario respectivo y hallar sus recorridos: 100, 50, 40, 60, 150, 111, 165.

[pic 13]

Pre-orden(R-SI-SD)

100,50, 40, 60, 150, 111, 165

In-orden (SI-R-SD)

40, 50, 60, 100, 111, 150, 165

Post-orden(SI-SD-R)

40, 60, 50,100, 111, 165, 150

2.