ARBOLES

ARBOLES

estructura de datos ramificada (no lineal)
1. puede representarse como un conjunto de nodos enlazados entre sí por medio de ramas
permiten modelar diversas entidades del mundo real tales como, por ejemplo, el índice de un libro, la clasificación del reino animal, el árbol genealógico de un apellido, etc.
1. se dice que un árbol es completo cuando todos sus nodos (excepto las hojas) tienen el mismo grado y los diferentes niveles están poblados por completo.
Arboles Binarios
1. Recorridos. Se entiende por recorrido el tratamiento realizado para acceder a los diferentes nodos de un árbol.
  1. el recorrido se puede realizar basándose en las siguientes modalidades:
    1. En profundidad. Se progresa verticalmente desde la raíz hacia las hojas y, en principio, de izquierda a derecha.
      1. Preorden. La clave se procesa en primer lugar.
      2. Postorden. Se desciende recursivamente por la rama izquierda, al alcanzar el final de dicha rama, se retorna y se desciende por la rama derecha
      3. Orden central. Se desciende recursivamente por la rama izquierda
2. .Búsqueda.
  1. por ejemplo: ejemplo si se implementa un método (búsqueda) que recibe como argumentos un árbol y una clave (ambos pasados por valor) y devuelve true si dicha clave se encuentra en el árbol, y false en caso contrario.
  2. Creación de un árbol.
    1. Para insertar claves en un árbol es necesario establecer previamente un criterio. Normalmente no se permite insertar claves repetidas
  3. Tratamiento de hojas. En este tipo de algoritmos se trata de evaluar la condición de que un nodo del árbol sea una hoja
Arboles Binarios De Busqueda
1. Algoritmos de consulta.
2. Un árbol binario de búsqueda es un tipo de árbol binario en el que se verifica para todo nodo que las claves de su subárbol izquierdo son menores que las de dicho nodo y las claves de su subárbol derecho son mayores.
3. Algoritmos de modificación.
  1. Inserción. Se trata de crear un nuevo nodo en la posición que le corresponda según el criterio de árbol binario de búsqueda.
4. Eliminación: eliminación de un nodo en un árbol binario de búsqueda implica una reorganización posterior del mismo con el objeto de que una vez eliminado el nodo el árbol mantenga su naturaleza de búsqueda
Arbol Sobre Matriz
1. Clases y constructores
2. Recorridos en profundidad
3. Búsqueda. Para realizar una búsqueda en un árbol binario de búsqueda sobre matriz, es necesario comprobar primero si no hemos llegado a un nodo vacío (if (i != NULL), en cuyo caso devolveremos false como resultado), y luego vamos avanzando por la rama correspondiente
4. Inserción. Para realizar la inserción en un árbol binario de búsqueda sobre matriz, es necesario comprobar primero si todavía no está lleno el árbol (comprobando la variable miembro numNodos). Si se va a insertar en un árbol vacío, la inserción se hará en el método de llamada (insertar)
5. Eliminación
Conceptos Generales
1. Al nodo base, debe ser único, se le denomina raíz se representa gráficamente en la parte superior.
2. En un árbol se representa una relación jerárquica a partir del nodo raíz en sentido vertical descendente, definiendo niveles1 . El nivel del nodo raíz es 1.
3. Desde la raíz se puede llegar a cualquier nodo progresando por las ramas y atravesando los sucesivos niveles estableciendo así un camino
4. Se dice que un nodo es antecesor de otro cuando ambos forman parte de un camino y el primero se encuentra en un nivel superior
5. La relación entre dos nodos separados de forma inmediata por una rama se denomina padre/hijo.
6. Se denomina grado al número de hijos de un nodo.
7. Se dice que un nodo es hoja cuando no tiene descendientes (grado 0).
Atributos De Un Arbol
1. Altura / profundidad / nivel
2. Amplitud / Anchura: El número de nodos del nivel más poblado
3. Grado: el mayor de los grados de los nodos

Next up

Description

Resource summary

Media attachments

Similar

	Created by aracely santiago over 10 years ago