Algunas Caracteristicas y propiedades de los arboles

Definición de Árboles

• Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz.

•Un árbol de tipo T como una estructura homogenea, que es la concatenacion de un elemento tipo T junto con un número finito de árboles disjuntos, llamados subárboles

Algunas Caracteristicas y propiedades de los arboles

•Todo arbol que no este vacio, tiene un nodo unico raiz

•Si un nodo X es apuntado por el nodo Y. Se dice que X es hijo de Y

•X es antesesor de Y si el nodo X apunta al nodo Y. X es padre de Y

•Todos los nodos que son descendientes directos(hijos) de un mismo nodo(padre), son hermanos.

•Si un nodo no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja

•Todo nodo que no es raiz, ni hoja se conoce como nodo interior.

•Grado es el numero de descendientes directos de un nodo, grado de un arbol es el maximo grado de todos los nodos del arbol

•Nivel es el numero de arcos que deben recorrerse para lleagar a un nodo. Raiz tiene nivel 1

•Altura del arbol es el maximo número de niveles de todos los nodos del árbol.

Árboles Binarios

•Un arbol binario cada nodo puede tener como maximo dos subarboles y siempre es necesario distinguir entre el subarbol izquierdo y el subarbol derecho

•Arbol binario tipo T es una estructura homogenea que es la concatenacion de un elemento tipo T, llamado raiz, con dos arboles binarios disjuntos, llamados subarbol izquierdo y subarbol derecho.

•Se pueden aplicar para representar un arbol genealogico o para representar expresiones algebraicas construidas con operadores binarios

•Distintos. Cuando sus estructuras son diferentes

•Similares. Cuando sus estructuras son identicas pero la informacion que contiene cada arbol es diferente.

•Equivalentes. Cuando son similares y ademas la informacion es identica entre los dos arboles.

•Se dice que un árbol binario está lleno si es un árbol binario de profundidad k que tiene (2^k) - 1 nodos. Un árbol binario lleno es aquel que contiene el número máximo de posibles nodos. Como en estos casos no existen subárboles vacíos excepto para los nodos terminales.

•Un árbol binario con n nodos y profundidad k se dice que es completo si y sólo si sus nodos se corresponden con los nodos numerados de 1 a n en el árbol binario lleno de profundidad k. Definimos un árbol binario completo (ABC) como un A.B.lleno pero con sus hojas dispuestas de tal manera que las hojas del nivel más bajo están situadas tan a la izquierda como sea posible.

Estructuras de datos Heap (montículo)

•Un árbol completo, es aquel en el que todos los niveles, con excepción del último, tiene sus nodos completos. Un arbol perfectamente equilibrado hasta el penultimo nivel, y en el ultimo nivel los nodos se encuentran agrupados a la izquierda . •Un Heap es un árbol binario completo a izquierda, que permite implementar una cola con prioridad, y donde los elementos se almacenan cumpliendo la propiedad de que la clave de un nodo siempre es mayor (o menor) que la clave de cualquiera de sus hijos. Lo que nos asegura que la raíz del árbol, en un Heap, siempre es el elemento mayor (o menor) de la estructura.

•El acceso a los elementos del Heap en un arreglo, se hace a través de algunas operaciones aritméticas básicas:

Left(i) : return 2*i .- Obtiene el hijo izquierdo del elemento i.

Right(i) : return 2*i +1 .- Obtiene el hijo derecho del elemento i.

Parent(i): return floor(i/2) .- Obtiene el padre del elemento i.•

•Crear un arbol binario

Carga(nodo)

1.- Leer informacion(info)

2.- Hacer nodo^.info=info

3.- Escribir “Existe nodo por la izquierda?”

4.- Leer repuesta

5.- Si respuesta es afirmativa

entonces

crea(otro)

hacer nodo^.izq=otro

regresar a carga(nodo^.izq)//llamada recursiva

sino

hacer nodo^.izq=Nil

6.- fin del paso 5

7.- 3.- Escribir “Existe nodo por la derecha?”

8.- Leer repuesta

9.- Si respuesta es afirmativa

entonces

crea(otro)

hacer nodo^.der=otro

regresar a carga(nodo^.der)//llamada recursiva

sino

hacer nodo^.der=Nil

10.- fin del paso 9

Recorridos en arboles

•Recorrido en preorden

1.-Visita la raiz

2.- recorre el subarbol izquierdo

3.-

...