Arboles (programacion)

1) Concepto de árboles

Los árboles son estructuras de datos no lineales que se utilizan para representar fórmulas algebraicas, para organizar objetos en orden de tal forma que las búsquedas sean muy eficientes y en aplicaciones diversas tales como inteligencia artificial o algoritmos de cifrado.

2) Arboles Binarios

Un árbol binario es una estructura recursiva ya que es un árbol cuyos nodos no pueden tener más de 2 subárboles. Cada nodo puede tener cero, uno o dos hijos.

3) Elementos de un árbol

Un árbol consta principalmente de un conjunto finito de elementos llamados nodos y de un conjunto finito de líneas dirigidas llamadas ramas.

a) Raíz: El primer nodo de un árbol.

b) Arcos o ramas: Las flechas que conectan un nodo con otro.

c) Hojas o nodos terminales: Los nodos que no conducen a ningún nodo.

d) Camino: Es la secuencia de arcos contiguos.

e) Longitud: Es el número de ramas de un camino.

f) Nivel de un nodo: Es la longitud del camino que conecta el nodo al nodo raíz.

g) Al tura de árbol: Es la longitud del camino más largo que conecta la raíz a una hoja.

h) Subárbol: Es un conjunto de nodos del árbol conectados por ramas del propio árbol.

4) Sentencia para crear un árbol

Se usan conceptos básicos de listas enlazadas, con la diferencia de que cada nodo puede señalar varios nodos a la vez.

public class nodo{

protected Object dato;

protected nodo izdo;

protected nodo dcho;

public nodo (Object valor){

dato = valor;

izdo = null;

dcho = null;

}

public Nodo (Nodo ramaIzdo, Object valor, Nodo ramaDcho){

this(dato);

izdo = ramaIzdo;

dcho = ramaDcho;

}

5) Árbol de expresión

Una expresión es una secuencia de tokens. Un token puede ser un operando o un operador. Un árbol de expresión es un árbol binario con las siguientes expresiones:

a) Cada hoja es un operando.

b) Los nodos raíz y los nodos internos son operadores.

c) Los subárboles son subexpresiones cuyo nodo raíz es un operador.

Por ejemplo la expresión a * (b + c) + d tiene el siguiente árbol de expresión.

6) Árbol de búsqueda

Es aquel en que dado un nodo, todos los datos del subárbol izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que sus propios datos. La principal utilización de una estructura de árbol binario de búsqueda está en la implementación de los índices en las bases de datos. Los Sistemas de Administración de Bases de Datos Relacionales utilizan objetos almacenados en el disco llamados índices, que se utilizan para acceder rápidamente a los datos de una tabla, ordenando uno o más campos de esa tabla y recuperando los valores ordenados mediante árboles binarios de búsqueda. Estos árboles, por supuesto, son guardados en el disco.

Además de esta utilización, los árboles binarios de búsqueda sirven para implementar mapas, también llamados arreglos asociativos, que consisten en listas ordenadas de pares <clave, valor>, en donde se puede acceder al objeto valor mediante

...