8.4 Arboles
Se utilizan para representar una jerarquia.
Tipos de Arboles
- Libres: No se identifica claramente un nodo raiz
- Raiz
- Arbol de expansion -> Se asocian recursos en las conexiones entre nodos.
- Binarios
Altura y Nivel de un Arbol
- El nodo raiz esta siempre en el nivel 0, los nodos que dependen del nodo raiz estan en el nivel 1 y asi sucesivamente.
- La altura es el numero de niveles
- Segun el nodo raiz identificado depende la altura y el nivel.
Conceptos
- Sub Arboles
Es un arbol que forma parte de otro arbol mas grande.
- Vertices terminales
Es donde termina el arbol. No posee nodos hijos, a estos vertices o nodos se les denomina HOJAS.
- Vertices internos
Al contrario de los terminales, son los vertices que siguen teniendo conexiones y permiten que el arbol se siga expandiendo. Son los vertices que tienen hijos.
- Arbol binario
Es donde maximo tenemos dos hijos por cada vertice.
Tipos de arbol binarios
- Binario completo: tiene dos hijos o no tiene ninguno
- Binario lleno: todos los nodos llegan a un mismo nivel.
- Degenerado: la mayoria de sus vertices tienen solo un hijo.
- Estructura recursiva
- El arbol bianrio tiene una estructura recursiva, significa que se puede llamar asi mismo, podemos descomponer un arbol muy gran o iteraciones en partes mas pequeñas.
- Arbol de expansion
- Un árbol de expansión es donde tenemos todos los nodos conectados entre si, pero tenemos un numero asociado a cada conexión.
- El número representa una unidad, un recurso o un coste que debemos asumir para conectar los nodos entre si.
- Cuando buscamos el nodo de expansión mínimo, lo que estamos buscando es como conectar todos los nodos entre si y que cueste lo mínimo
Recorrido de arboles
- Preorden
- Se lee la raiz, luego el nodo izquierdo y por ultimo el nodo derecho.
- Se utiliza la misma secuencia para recorrer el arbol. El primero sera nuestro nodo raizm despues pasaremos al siguiente nodo raiz hasta llegar al nodo temrinal que no tenga mas nodos raiz, en ese caso anotaremos el nodo izquierdo terminal y pasaremos al nodo derecho.
- In Orden
- Se lee el nodo izquierdo, luego el nodo raiz y por ultimo el nodo derecho.
- Para entender bien el proceso de recorrido in orden, lo que hacemos realmente es recorrer el árbol binario hasta llegar al nodo izquierdo terminal, ese sera nuestro primero nodo, despue anotaremos la raíz de donde salio ese nodo izquierdo terminal
- Depués pasaremos al nodo derecho y si es un nodo raíz lo recorreremos hasta hallar el nodo izquierdo terminal y de nuevo apuntaremos la raíz de donde salio y pasaremos al nodo derecho hasta hallar el nodo derecho terminal
- Cuando consigamos recorrer todo el lado izquierdo del árbol podremos anotar su nodo raíz principal que fue de donde salieron todos los nodos del lado izquierdo
- Pasaremos a proceder al lado derecho del árbol haciendo los mismos proceso.
- Pos Orden
- Se lee primero el nodo izquierdo, luego el nodo derecho y por ultimo el nodo raiz.
- Es igual que el anterior solo que en un diferente orden
Expresiones Aritméticas
Reglas para expresiones aritmeticas en arboles
- Los vertices son operandos (numeros)
- Los vertices internos son operadores
- La raiz debe ser siempre un operador
Así como vimos las diferentes formas para recorrer un árbol, las expresiones aritméticas tienen también sus propias formas:
- Pre fijo: raíz-izquierda-derecha
- In fijo: izquierda-raíz-derecha
- Pos fijo: izquierda-derecha-raíz
Backlinks: Inteligencia Artificial:8. Matematicas discretas