Clases para la implementacion de listas
Los métodos básicos que deben de tener estas implementaciones son:
• Insert ( x, p ), insert el elemento x en la posición p
• end (), va a la posición final de datos.(No necesariamente la del arreglo).
• Locate ( x ), retorna la posición del elemento x.
• Retrieve ( p ), retorna el elemento en la posición p.
• Delete ( p ) ,Delete ( x ),Borra la posicion p. Borra el o los elementos x.
• Next () ,Next ( p ), Posición siguiente o posición siguiente a p. La posición.
• end (), va a la posición final de datos.(No necesariamente la del arreglo).
• Locate ( x ), retorna la posición del elemento x.
• Retrieve ( p ), retorna el elemento en la posición p.
• Delete ( p ) ,Delete ( x ),Borra la posicion p. Borra el o los elementos x.
• Next () ,Next ( p ), Posición siguiente o posición siguiente a p. La posición.
Pues la verdad se le entendía y se pudo explicar el tema aunque le fato mas material
Representación en memoria de arboles
Los nodos del árbol binario serán representados como registros que
contendrán como mínimo tres campos. En un campo se almacenará la
información del nodo. Los dos restantes se utilizarán para apuntar al
sub arbol izquierdo y derecho del sub arbol en cuestión.
Pues en este tema estuvo muy confuso ya que no veni algo preparado y le falto material y unos ejemplos.
Arboles binarios
Recorrido de un Árbol Binario
Hay tres manera de recorrer un árbol : en inorden, preorden y postorden.
Hay tres manera de recorrer un árbol : en inorden, preorden y postorden.
Cada una de ellas tiene una secuencia distinta para cada recorrido.
Cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden
tener más de dos hijos. Si algún hijo tiene como referencia a null, es
decir que no almacena ningún dato, entonces este es llamado un nodo
externo.
En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda. Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos. Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos. Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).
En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda. Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos. Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos. Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).
Pues en este tema se le entendió y si sabia de lo que trataba el tema y también tuvo ejemplos para guiarse y los explico muy bien.
Recorrido en un árbol binario
Preorden: (raíz,
izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay
que realizar las siguientes operaciones recursivamente en cada nodo, comenzando
con el nodo de raíz:
1. Visite la raíz
2. Atraviese el
sub-árbol izquierdo
3. Atraviese el
sub-árbol derecho
Inorden: (izquierdo, raíz,
derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay
que realizar las siguientes operaciones recursivamente en cada nodo:
1. Atraviese el
sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el
sub-árbol derecho
Postorden: (izquierdo,
derecho, raíz). Para recorrer un árbol binario no vacío en
postorden, hay que realizar las siguientes operaciones recursivamente en cada
nodo:
1. Atraviese el
sub-árbol izquierdo
2. Atraviese el
sub-árbol derecho
3. Visite la raíz
En general, la diferencia entre
preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se
recorre primero el sub-árbol izquierdo y luego el derecho.
·
En preorden, la raíz se recorre antes que los recorridos de los sub árboles
izquierdo y derecho
·
En inorden, la raíz se recorre entre los recorridos de los árboles
izquierdo y derecho, y
·
En postorden, la raíz se recorre después de los recorridos por el
sub árbol izquierdo y el derecho
Preorden (antes), inorden (en medio),
postorden (después).
Pues también supieron explicar muy bien el tema que les toco y dieron varios ejemplos
Árbol binario de búsqueda
También llamados BST (acrónimo del inglés Binary Search Tree) es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.
La mayoría de los árboles binarios son de búsqueda
Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
En caso de tener sub árbol izquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el sub árbol izquierdo, y que el sub árbol izquierdo sea un árbol binario de búsqueda.
En caso de tener sub árbol derecho, la raíz R debe ser menor que el valor mínimo almacenado en el sub árbol derecho, y que el sub árbol derecho sea un árbol binario de búsqueda.
Un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.
Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación esté definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.
GRAFOS
En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos. Existen diferentes implementaciones del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas y multilistas de adyacencia (no acotadas)
Tipos de Grafos:
Grafos simples
Grafo completo
Grafo conexo
