12 ARBOLES

ARBOLES

ESTRUCTURAS DE DATOS

INTRODUCCION


Las listas enlazadas son estructuras lineales






Son flexibles pero son secuenciales, un elemento detrás de otro

Los árboles


Junto con los grafos son estructuras de datos no lineales



Superan las desventajas de las listas



Sus elementos se pueden recorrer de distintas formas, no
necesariamente uno detrás de otro

Son muy útiles parala búsqueda y recuperación de
información

CONCEPTO

A es Padre
B y C hijos de A:
hermanos
B es Padre
D, E, F hijos de B



Estructura que organiza sus elementos formando
jerarquías: PADRES E HIJOS



Los elementos de un árbol se llaman nodos



Si un nodo p tiene un enlace con un nodo m,


p es el padre y m es el hijo



Los hijos de un mismo padre se llaman: hermanos

A
B
D



Todos losnodos tienen al menos un padre, menos la raíz: A



Si no tienen hijos se llaman hoja: D, E, F y C



Un subárbol de un árbol


Es cualquier nodo del árbol junto con todos sus
descendientes

C

E

F

B
D

E

F

TERMINOLOGIA




Camino: Secuencia de nodos conectados dentro de un arbol
Longitud del camino: es el numero de nodos menos 1 en un camino
Altura del árbol: es el nivel mas alto delárbol





Nivel(profundidad) de un nodo: es el numero de nodos entre el nodo
y la raíz.
Nivel de un árbol





Un árbol con un solo nodo tiene altura 1

Es el numero de nodos entre la raíz y el nodo mas profundo del árbol, la altura
del un árbol entonces

Grado(aridad) de un nodo: es numero de hijos del nodo
Grado(aridad) de un árbol: máxima aridad de sus nodos

TDA ARBOL : DEFINICIONINFORMAL


Valores:

Conjunto de elementos, donde SOLO se conoce el nodo raíz
 Un nodo puede almacenar contenido y estar enlazado con






Sus árboles hijos (pueden ser dos o varios)

Operaciones: Dependen del tipo de árbol, pero en general tenemos


Vaciar o inicializar el Arbol




Eliminar un árbol




void Arbol_Eliminar(Arbol *A);

Saber si un árbol esta vacío




void Arbol_Vaciar(Arbol *A);

bool Arbol_EstaVacio(Arbol A);

Recorrer un árbol
void PreOrden(Arbol A)
 void EnOrden(Arbol A)
 void PostOrden(Arbol A)


TDA ARBOL: DEFINICION
FORMAL
::= <> |
::= {}
::= <>{<>}

ARBOLES BINARIOS




C

B

Tipo especial de árbol




A

D

Cada nodo no puede tener mas de dos hijos

Un árbol puede ser unconjunto


Vacío, no tiene ningún nodo



O constar de tres partes:


Un nodo raíz y



Dos subárboles binarios: izquierdo y derecho

La definición de un árbol binario es recursiva


La definición global depende de si misma

RAIZ

A
B
D
H
Sub.
Izq.

C
E

I

F

G
J

Sub.
Der.

DEFINICIONES
RECURSIVAS
La definición del árbol es recursiva







A

Se basa en si misma

B

La terminología de losárboles


C

D

También puede ser definida en forma recursiva

Ejemplo: NIVEL de un árbol


SUB. DER.
Nivel 1

E

Identificar el caso recursivo y el caso mas básico

nivel 1

A

Caso Básico
Un árbol con un solo
nodo tiene nivel 1

S. izq.
Nivel
1

A
B

C

S. der.
Nivel 1

Nivel Del Arbol:
2

SUB.
SUB. IZQ.
IZQ.
SUB. IZQ.
Nivel
==3 1 +
Nivel
SUB.
DER..
Nivel
=
Max(0,2) 1 +
Max(0,Sub.Izq)
Nivel = 1Max(0,Sub.Izq.)
Max(0,1)
NIVEL
: MAX(S.IZQ,
1 + MAX(3,
1)
NIVEL
: 1 +NIVEL
:4
S.DER)

Caso Recursivo
Si tiene mas de un nodo, el nivel es:
1 + MAX(Nivel(SubIzq), Nivel(SubDer))

ARBOLES BINARIOS
LLENOS
 Un árbol de altura h, esta lleno si





Todas sus hojas esta en el nivel h
Los nodos de altura menor a h tienen siempre 2 hijos

Recursiva


Si T esta vacío,




Entonces T es un árbolbinario lleno de altura 0

Si no esta vacío, y tiene h>0


Esta lleno si los subárboles de la raíz, son ambos árboles
binarios llenos de altura h-1

ARBOLES BINARIOS
COMPLETOS




Un arbol de altura h esta completo si


Todos los nodos hasta el nivel h-2 tienen
dos hijos cada uno y



En el nivel h-1, si un nodo tiene un hijo
derecho, todas las hojas de su subarbol
izquierdo están a nivel h...

Leer documento completo

Regístrate para leer el documento completo.