4unidad de contabilidad

Unidad 4 Estructuras no Lineales
4.1 Arboles Definición

Un árbol es una estructura de datos ampliamente usada que emula 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 (en ese
caso, tambiéndecimos que b es hijo de a). 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 define como una estructura de datos no lineal. Esta estructura
se usa principalmente para representar datos con una relación jerárquica entre sus
elementos, como por ejemplo registros, árboles genealógicos y tablas de
contenidos. Entreotros tenemos un tipo especial de de árbol que es, llamado árbol
binario, que puede ser implementado fácilmente en la computadora.

4.1.2 Representación en Memoria de Arboles

Las operaciones comunes en árboles son:
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).
Encontrar la raíz de cualquier nodo.
A_1, A_2 \dots
n_1, n_2, \dots, n_k
N_1, N_2, \dots,N_k
N = 1 + N_1 + \dots + N_k
n_1, n_2, \dots, n_k
A_1, A_2 \dots A_k
A_2 \dots A_k
A_1, A_2 \dots A_k
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.

4.1.2.1 Arboles Generales

Formalmente, podemos definir un árbol de la siguiente forma:

Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
Un nuevo árbol a partir de un nodo nr y kárboles
de raíces
n1, n2,……..nk conN1, N2,……….Nk elementos cada uno, puede
construirse estableciendo una relación padre-hijo entre nr y cada una de las
raíces de los k árboles. El árbol resultante N=1+N1+………….Nk de nodos
tiene como raíz el nodo nr, los nodos son los hijos de nr y el conjunto de
nodos hoja está formado por la unión de los k conjuntos hojas iníciales. A
cada uno de los árbolesAi se les denota ahora subárboles de la raíz.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos
consecutivos de la sucesión haya una relación de parentesco, decimos que es un
recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol:
primero en profundidad y primero en anchura. En el primer caso, se listan los
nodos expandiendo el hijo actual decada nodo hasta llegar a una hoja, donde se
vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el
segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1
aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos
típicos del árbol son preorden, postorden e inorden:
El recorrido en preorden, también llamado ordenprevio consiste en
recorrer en primer lugar la raíz y luego cada uno de los hijos en orden
previo.
El recorrido en inorden, también llamado orden simétrico (aunque este
nombre sólo cobra significado en los árboles binarios) consiste en recorrer
en primer lugar A1, luego la raíz y luego cada uno de los hijos en orden
simétrico.
El recorrido en postorden, también llamado orden posterior consisteen
recorrer en primer lugar cada uno de los hijos en orden posterior y por
último la raíz.
Finalmente, puede decirse que esta estructura es una representación del concepto
de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico 180pxBinary_tree_%28oriented_digraph%29.png

4.1.2.2 Arboles Binarios

En ciencias de la computación, un árbol binario es una estructura de datos en...