Arboles estructura de datos

Introduccion 1

Definicion 2

Clasificacion 3

Terminos de los arboles 4

Operaciones basicas de los arboles` 5

Recorrido de un arbol binario 6

Algoritmo de arboles 7

Implementacion 9

Conclusion 10

Fuentes de informacion 11

INTRODUCCION:

En este trabajo veremos la estructura de datos no lineales llamada árbol. Esta estructura se usa principalmentepara representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos, y tablas de contenidos. Vamos a profundizar en un tipo especial de árbol llamado árbol binario, la cual puede ser implementado fácilmente en la computadora; aunque en un árbol puede parecer muy restrictivo. También se va a ampliar sobre árboles más generales y puntos conrelación a los árboles binarios; entre estos tenemos a la terminología, los árboles binarios complementos, árboles binarios de búsqueda, búsqueda e inserción en árboles binarios de búsqueda, árboles generales, representación de árboles generales en la computadora y correspondencia entre los árboles generales y árboles binarios.

DEFINICION:

Un árbol es una estructura de datos ampliamente usada queemula la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o mas nodos hijos conectados a él. Se dice que un nodo ‘a’ es padre de un nodo ‘b’ si existe un enlace desde ‘a’ hasta ‘b’. Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja.

El árbol También se definecomo una estructura de datos no lineal.

CLASIFICACION DE ARBOLES:

* Árbol binario distinto: Se dice que un árbol es distinto cuando su estructura grafica es diferente.

* Árbol binario similar: Se dice que un árbol es similar cuando su estructura grafica es idéntica pero la información que contiene entre sus nodos es diferente.

* Árbol binario equivalente: Son aquellos que suestructura grafica es idéntica pero además la información entre sus nodos.

* Árbol binario completo: son aquellos que todos sus nodos excepto el último nivel tienen sus dos hijos.

* Árbol binario lleno: es aquel que tiene su número máximo de posibles nodos.

TERMINOS DE LOS ARBOLES:

a) Todo arbol que no es vacio, tiene un unico nodo raiz.
b) Un nodo X es desendientedirecto de un nodo Y, si el nodo X es apuntado por el nodo Y. En este caso es comun utilizar la expresion X es hijo de Y.
c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. En este caso es comun utilizar la expresion X es padre de Y.
d) Se dise que todos los nodos que son desendientes directos (hijos), de un mismo nodo (padre), son hermanos.
e) Todo nodo que notiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
f) Todo nodo que no es raiz, ni terminal u hoja se conoce con el nombre de interior.
g) Grado es el numero de desendientes directos de un determinado nodo. Grado del arbol es el maximo grado de todos los nodos del arbol.
h) Nivel es el numero de arcos que deben ser recorridos para llegar a un determinado nodo.Por defiicion la raiz tiene nivel 1.
i) Altura del arbol es el maximo numero de niveles de todos los nodos del arbol.

OPERACIONES BASICAS DE LOS ARBOLES:

Enumerar todos los elementos.
Buscar un elemento.
Dado un nodo, listar los hijos (si los hay).
Borrar un elemento.
Eliminar un subárbol (algunas veces llamada podar).
Añadir un subárbol (algunas veces llamada injertar).
Encontrarla raíz de cualquier nodo.
Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:
Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.
Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array.

RECORRIDO DE UN ARBOL BINARIO:...