Arboles - java

INGENIERIA DE SISTEMAS

19

ESTRUCTURAS DE DATOS (Listas simples)

ARBOLES
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar unadefinición recursiva: “un árbol es una estructura compuesta por un dato y varios árboles”. Estas definiciones son simples, pero, las características que implican no lo son tanto. Componentes de unárbol A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

Una característica importante de los árboles es que cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodosólo tendrá un padre. Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, L y M son hijos de G. Nodo padre: Nodo del que salen otros nodos. En el ejemplo B espadre de E y F Nodo raíz: nodo que no tiene padre, Nodo hoja: nodo que no tiene hijos. Del ejemplo, K,F,L,M,H,I,N,O son nodos hoja. Cada nodo en un árbol está ubicado en un nivel determinado, empezandopor la raíz que se encuentra en el nivel cero (0), sus hijos en el nivel 1, 2, y así sucesivamente, hasta la profundidad o altura que corresponde al máximo nivel del árbol. Orden: es el número máximode hijos que puede tener cada elemento del árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Losarboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios ARBOLES BINARIOS Es un árbol especial donde cada nodopadre como máximo tiene dos hijos, denominados como hijo izquierdo y derecho.

INGENIERIA DE SISTEMAS ARBOLES BINARIOS DE BÚSQUEDA (ABB)

20

ESTRUCTURAS DE DATOS (Listas simples)

Se trata dearboles en los que se cumple que para cada nodo, el valor del nodo izquierdo de cada raíz es menor que el valor del nodo raíz y que el valor del nodo derecho de la raíz. raiz 6

4

12

2...