Representación y manipulación de árboles: búsqueda y recorrido

Arboles

Intuitivamente el concepto de árbol implica una estructura donde los datos se organizan de modo que los elementos de información estén relacionados entre sí a través de ramas.

• Nodos: conjunto finito de elementos.

• Ramas: conjunto finito de líneas dirigidas, que conectan nodos.

• Grado del Nodo: número de ramas descendentes con un nodo.

• Raíz: primer nodo de un árbol no vacío.

• Camino: secuencia de nodos en los que c/nodo es adyacente al siguiente.

– Solo existe 1 camino entre la Raíz y un Nodo cualquier.

– La distancia de un Nodo a la Raíz determina la rapidez de búsqueda.

Orden de árbol

 Cada nodo contiene un dato. Para ordenamiento, se requiere una función de precedencia y una regla de orden del árbol. La regla establece el orden relativo de los datos del padre y sus hijos.  El grado de un nodo es la cantidad de hijos que tiene.  En árboles ordenados, también el orden de los hijos de un nodo se tiene que fijar (de izquierda a derecha). Depende de la aplicación si habrá datos duplicados o si serán únicos todos.

Estructura típica de un nodo

Cada nodo será una estructura o registro que dispondrá de varios campos, y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura. Los nodos son herramientas esenciales para la construcción de estructuras de datos dinámicas.

 referencias:

http://www.ucema.edu.ar/u/rst/Algoritmos_y_Estructura_de_Datos/Teoria/5._Arboles_binarios.pdf