Arboles Java

Arboles
Estructura de Arbol.
Un árbol es otra clase de estructura de datos que puede definirse como: Una estructura de árbol como tipo Base T es:
• Una estructura vacia
• Una estructura T ligada con un número finito de estructuras de árbol disjuntas asociadas de tipo base T, llamadas subárboles.

Un árbol se puede representar de diferentes formas:K O F H

I J E P

D L M N

B G C
A

Conjuntos anidados
(A(B(D(I),E(J,K,L), C (F(O),G(M,N),H(P) ) ) )Paréntesis anidados

A

B C

D E F G H

I J K L O M N P
Gráfica
La raíz de unárbol es el nodo superior y tiene nivel 0. Un nodo Y que esta directamente debajo de otro nodo X, se llama descendiente o hijo de X. Si un nodo no tiene descendientes se llama nodo terminal u hoja. Un nodo no terminal se llama nodo interior. El grado de nodo es igual al número de descendientes.

Si, X está en el nivel i, y Y es hijo de X, entonces Y está en el nivel i+1. El nivel máximo de unárbol es su profundidad o altura. El número de ramas o aristas que tiene que ser recorridas desde la raíz hasta un nodo x se llama longitud de trayectoria de x. La longitud de trayectoria de un árbol es la suma de las longitudes de trayectoria de todos sus componentes.

Un árbol es perfectamente balanceado, si para cada nodo los números de nodos de sus subárboles izquierdo y derecho difieren cuandomás en 1.

Los árboles de grado 2 son un caso particular, llamados árboles binarios. Un árbol binario ordenado se define como un conjunto de nodos finito de elementos que es vacío o consta de una raíz con dos subárboles binarios disjuntos llamados subárbol izquierdo y derecho de la raíz. Los árboles de grado mayor a 2 se llama árboles multicamino o multimodales.

La representación de unárbol puede ser:
NULL para un árbol vacío
o
class NodoArbol{
NodoArbol nodoIzquierdo;
int datos;
NodoArbol nodoDerecho;
………….
}
Las operaciones que se realizan con estructuras de árbol, son más complejas que las listas. Las principales operaciones sobre árboles son:

• Inserción de un nuevo nodo.
• Eliminación o borrado de un nodo.
• Recorrido de un árbolo En preorden
o En orden
o En postorden
• Búsqueda de un elemento.
• Balanceo del árbol.

Los árboles binarios se usan para representar un conjunto de datos cuyos elementos se recuperan a través de una llave única.

Creación del árbol.
La construcción de un árbol se puede hacer bajo dos criterios:

• Insertando los nuevos nodos dependiendo de la llave.
•Creando un árbol balanceado.

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

Un árbol de búsqueda es aquel que se organiza de tal forma que para cada nodo ti todas las llaves en el subárbol izquierdo de ti sean menores que la llave de ti y aquellas en el subárbol derecho sean mayores que la llave de ti.

En un árbol de búsqueda es posible localizar una llave comenzando la búsqueda en la raíz y siguiendouna trayectoria de búsqueda seleccionando un subárbol izquierdo o derecho por una decisión basada en la inspección de la llave del nodo.

class NodoArbol{
NodoArbol nodoIzquierdo;
int datos;
NodoArbol nodoDerecho;

public NodoArbol(int datosNodo){
datos=datosNodo;
nodoIzquierdo=nodoDerecho=null;
}

public void insertar(int valorInsertar){

//inserta en...