resumen ed u4

Resumen unidad 4
Arboles
ÁRBOL: El conjunto de nodos y el conjunto de aristas que conectan pares de esos nodos.
Usos Sistemas de archivos (directorios)
Traductores (árboles desintaxis)
Algoritmos de búsqueda
Árbol con raíz: Tiene un nodo principal del que “cuelgan” los demás ,1 y sólo 1 nodo raíz, todo nodo, excepto la raíz, tiene 1 solo padre y todo padre tiene almenos 1 hijo hay un único camino, desde la raíz, para llegar a cada nodo.
Profundidad.- Número de aristas a atravesar para llegar un nodo desde la raíz
Altura.- Número de aristas para llegar de unnodo hasta la hoja más profunda debajo de él
Tamaño.- Número de descendientes que tiene un nodo, incluyéndolo a él mismo
Grado.- Número de hijos
Nivel.- Número de antecesores desde la raíz + 1Para poder armar un árbol, se requieren nodos, éstos deberán guardar la información Y los apuntadores.
Si el nodo puede tener un número indefinido de hijos, se tendría que guardar: Dato, arreglodinámico de apuntadores a hijos o apuntador al primer hijo y al primer hermano.
Un árbol binario, siempre tiene de 0 a 2 hijos, lo que permite conocer los apuntadores (izquierdo y derecho). Estos pueden ser:Equilibrado.-Diferencia de altura entre hermanos es máximo una unidad
Perfectamente equilibrado.- No hay diferencia de altura entre hermanos
Completo.- Todos los nodos tienen 0 o 2 hijos.
Lleno.-Completo y todas las hojas al mismo nivel.
El recorrido es proceso que permite acceder una sola vez a cada uno de los nodos del árbol
Puede ser:
Por anchura.-Recorre cada nivel completo desde laraíz a las hojas, de izquierda a derecha
En profundidad.- Pre-Orden: primero el nodo y luego los hijos de izquierda a derecha
En-Orden: primero el hijo izquierdo, luego el nodo, luego el hijoderecho
Post-Orden: primero hijo izquierdo, luego hijo derecho, luego el nodo.



Búsqueda de ABB
En un árbol binario de búsqueda para cualquier nodo su valor es superior a los valores de los...