unidad v arboles

Árboles

Acerca de arboles

Los árboles representan las estructuras de datos no lineales y dinámicas mas importantes en computación

Dinámicas porque la estructura puede cambiar durante la ejecución del programa

No lineales, puesto que a cada elemento del árbol puede seguirle varios elementos

Estructuras estáticas y dinámicas

Estructuras estáticas Estructuras dinámicas

Arreglos Listas

Registros Árboles

Conjuntos

Estructuras lineales y no lineales

Estructuras lineales Estructuras no lineales

Arreglos Árboles

Registros

Conjuntos

Pilas

Colas

Listas

Árbol

Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, uno de los cuales es conocido como raíz. Además se crean relaciones o parentesco entre nodos dando lugar a términos como: padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

Definición formal de Árbol

Es una estructura homogénea que es la concatenación de un elemento junto con un número finito de árboles disjuntos, llamados subárboles. Una forma particular de árbol es la estructura vacía.

Aplicaciones de Árboles

Representar formulas matemáticas

Organizar adecuadamente información

Registrar la historia de un campeonato de tenis

Construir un árbol genealógico

Análisis de circuitos eléctricos

Enumerar los capítulos y secciones de un libro

Representacion de arboles

Diagramas de Venn

AB C

D

E F

G

E

Anidacion de paréntesis

(A(B(D(I,E,F(J,K)),C(G,H(L))))

Notación decimal DEWEY

1.A, 1.1.B, 1.1.1.D, 1.1.1.1.I, 1.1.2.E,1.1.3.F

Notacion indentada

A

B

D

L

G

J

I

E

CARACTERISTICAS Y PROPIEDADES DE LOS

ÁRBOLES TODO ARBOL QUE NO ES VACIO, TIENE UN UNICO NODO RAIZ.

UN NODO X ES DESCENDIENTE DE UN NODO Y, SI EL NODO X ESTA APUNTADO POR EL NODO Y. EN ESTE CASO SE UTILIZA LA EXPRESION X ES HIJO DE Y.

UN NODO X ES ANTECESOR DIRECTO DE UN NODO Y, SI EL NODO X APUNTA AL NODO Y. EN ESTE CASO SE UTILIZA LA EXPRESIÓN X ES PADRE DE Y.

SE DICE QUE TODOS LOS NODOS QUE SON DESCENDIENTES DIRECTOS DE UN MISMO NODO PADRE, SON HERMANOS.

TODO NODO QUE NO TIENE RAMIFICACIONES(HIJOS),SE CONOCE COMO TERMINAL U HOJA.

Continuacion…

TODO NODO QUE NO ES RAIZ , NI TERMINAL U HOJA SE CONOCE COMO “INTERIOR”.

GRADO.- ES EL NUMERO DE DESCENDIENTES DIRECTOS DE UN DETERMINADO NODO.

GRADO DEL ARBOL.- ES EL MAXIMO GRADO DE TODOS LOS NODOS DEL ARBOL.

NIVEL.- ES EL NUMERO DE ARCOS QUE DEBEN SER RECORRIDOS PARA LLEGAR A UN DETERMINADO NODO. POR DEFINICION LA RAIZ TIENE NIVEL 1.

ALTURA.- ES EL MAXIMO NUMERO DE NIVELES DE TODOS LOS NODOS DEL ARBOL.

GRAFOEjemplo

X

Y

Grafo ejemplo

A

CB

D H

L

EF

KI

G

J

Grafo ejemplo

LONGITUD DE CAMINO INTERNO

Es la suma de las longitudes de camino de todos los nodos del arbol.

1

*h

i

I

LCI n i

I = representa el nivel del arbol, h altura y ni el numero de nodos

en el nivel

EJEMPLO:

LCI= 1*1 + 2*2 + 5*3 +4*4 = 36

LA LCIM=LCI/n n Numero de nodos en el arbol

LONGITUD DE CAMINO EXTERNO

ARBOL EXTENDIDO.- es aquel en el que el número de hijos de cada nodo es igual al grado del árbol. Si alguno de los nodos no cumple la condición entonces se debe incorporar al mismo nodos especiales.

Ejemplo de Arbol extendido

A

CB

D H

L

E F

KI

G

J

1

2

*h

i

I

LCE ne i

LONGITUD DE CAMINO EXTERNO

Se define como la suma de las longitudes de camino de todos los nodos especiales del arbol. Se calcula por medio de:

1

2

*h

i

I

LCE ne i

Ejercicio(10 puntos)Dado el siguiente arbol

A

CB

F L MG

D

E IH J K

Calcular la longitud de camino interno y la

longitud de camino externo y la media de

cada uno de ellos

Árboles binarios

Un árbol ordenado es aquel en el que las ramas están ordenados. Los de grado dos son de especial atención, porque representan estructuras importantes en computación y son conocidas como árboles binarios.

En un árbol binario solo puede tener a lo máximo dos subárboles y es necesario distinguir entre el subárbol izquierdo y el subárbol derecho

Definición de Árbol Binario

Es una estructura homogénea que es la concatenación de un elemento de tipo T, llamada raíz, con dos árboles binarios disjuntos, llamados subárbol izquierdo y subárbol derecho de la raíz.

Una forma particular de árbol binario es la estructura vacía.

Aplicaciones

En estructura para tomar decisiones en dos opciones.

Para representar un árbol genealógico

Para representar la historia de un campeonato de tenis.

Para representar expresiones algebraicas construidas con operadores binarios.

Arbol binario de busqueda

27

14

50 77

47

7 3259

11

Representación algebraica(A * B) + (C / D) ^ 3

+

.

C D

^

A /3

B

Árbol GenealógicoOSVALDO CAIRO

BATTISTUTTI

MARIA BATTISTUTTI

VALIENTEJOSE CAIRO

SCANDALLO

MARIA VALIENTE

MARTIN

ANTONIO CAIRO

GODOY

MARIA SCANDALLO

MISCORIA

ROBERTO

BATTISTUTTI

MAZZOTTI

Arboles binarios

Distintos.-Cuando sus estructuras son diferentes

A

B

A

B

Arboles binarios

Similares.-Cuando sus estructuras son idénticas, pero la informacion

de sus nodos son diferentes

A

B

X

Y

A

B

Arboles binarios

Equivalentes.-Cuando son similares y ademas los nodos

contienen la misma información

A

B

A

B

EJEMPLOA

B

D

C

A

X

N

L

A

B

D

C

A

B

D

C

A) B)

C)

D)

C A

C B

C D

A,B Y D

A D

ARBOLES BINARIOS COMPLETOS

Es el árbol en el que todos sus nodos excepto los del último nivel, tienen dos hijos: el subarbol izquierdo y el subárbol derecho.

Formula para calcular el numero de nodos de un árbol binario completo de altura h

NUMERO DE NODOSABC = 2h – 1

Donde ABC significa árbol binario completo y h l altura del árbol

Ejemplo de árbol binario completo

A

B

F M

D

E J

Representación de árboles binarios en memoria

1.- Por medio de datos tipo puntero, conocido como variables dinámicas.

2.- Por medio de arreglos.

Los punteros es la forma mas natural para tratar este tipo de estructuras.

Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos.

IZQ.- Campo donde se almacena a dirección del subárbol izquierdo.

INFO.- Campo donde se almacena la información del nodo.

DER.- Campo donde se almacena a dirección del subárbol derecho.

IZQ INFO DERT

Definición de un árbol binario en lenguaje algorítmico.

Enlace = ^nodo

nodo = registro

izq: tipo enlace

info: tipo dato

der: tipo enlace

{fin de la definición}

Ejemplo de aplicación de árbol binario

( * ) ( / ) 3.5A B C D

+

*

B 3.5

^

A /

C D

Representación del árbol binario en Memoria

+

* ^

/A B 3.5

C D

RECORRIDOS EN ÁRBOLES BINARIOS

Una de las operaciones mas importantes en una árbol binario, es el recorrido de los mismos. Recorrer un árbol significa visitar los nodos del árbol en forma sistemática, de forma que todos los nodos del mismo sean visitados una sola vez.

Existen 3 formas de hacer el recorrido y son:

1.- PREORDEN

Visitar la raíz

Recorrer el subárbol izquierdo

Recorrer el subárbol derecho

Continuacion…2.- INORDEN

Recorrer el subarbol izquierdo

Visitar la raiz

Recorrer el subarbol derecho

3.- POSTORDEN

Recorrer el subarbol izquierdo

Recorrer el subarbol derecho

Visitar la raiz

Tarea(10 puntos)

Realizar un resumen sobre el tema “Árboles binarios de búsqueda”

Aspectos:

1.- Definición

2.- Búsqueda

3.- Inserción en un árbol binario de búsqueda

4.-Borrado en un árbol binario de búsqueda

5.- Manejar conceptos y algoritmos para cada tema.