Altura o profundidad (depth) de un árbol: Número máximo de nodos en una rama
Introducción
¿Qué es un grafo?
¿Qué es un árbol?
¿Qué es recursión?
Aplicaciones reales de grafos y árboles
Formas de representar un grafo
DFS
Análisis de DFS: algoritmo de búsqueda en profundidad
Programando DFS de forma recursiva
Otras formas de programar DFS
Recorridos y profundidad de un Árbol
Sum Root to Leaf Numbers: análisis del problema
Solución de Sum Root to Leaf Numbers
Playground: Sum Root to Leaf Numbers
Programando Sum Root to Leaf Numbers en Golang
Number of Islands: análisis del problema
Solución de Number of Islands
Playground: Number of Islands
Programando Number of Islands en Python
Ejercicios recomendados de DFS
Ejercicios resueltos de DFS
BFS
Análisis de BFS: algoritmo de búsqueda en anchura
Programando BFS con Python
Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema
Solución de Minimum Knights Moves
Playground: Minimum Knights Moves
Programando Minimum Knights Moves con Python
Rotting Oranges: análisis del problema
Solución de Rotting Oranges
Playground: Rotting Oranges
Rotting Oranges con Java
Shortest Bridge Between Islands: análisis del problema
Solución de Shortest Bridge Between Islands
Playground: Shortest Bridge Between Islands
Programando Shortest Bridge Between Islands con Python
Ejercicios recomendados de BFS
Ejercicios resueltos de BFS
Backtrack
Algoritmo de Backtrack
Letter Combinations of a Phone Number: análisis del problema
Solución de Letter Combinations of a Phone Number
Programando Letter Combinations of a Phone Number con C++
Playground: Letter Combinations of a Phone Number
Restore IP Addresses: análisis del problema
Programando Restore IP Addresses con C++
Playground: Restore IP Addresses
Word Search: análisis del problema
Solución de Word Search
Playgrund: Word Search
Programando Word Search JavaScript
Reto: N Queens Puzzle
Ejercicios recomendados de Backtrack
Ejercicios resueltos de Backtrack
Próximos pasos
¿Qué otros algoritmos y tipos de grafos puedes aprender?
¿Quieres más cursos avanzados de algoritmos?
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Aportes 6
Preguntas 0
Altura o profundidad (depth) de un árbol: Número máximo de nodos en una rama
InOrden: Recorre el sub-árbol izquierdo, luego visita el nodo raíz y recorre el sub-árbol derecho.
Pre-Orden: Visita el nodo raíz, recorre el sub-árbol izquierdo y recorre el sub-árbol derecho.
PostOrden: Recorre el sub-árbol izquierdo, recorre el sub-árbol derecho y visita el nodo raíz.
InOrden: Recorre el sub-árbol izquierdo, luego visita el nodo raíz y recorre el sub-árbol derecho. Pre-Orden: Visita el nodo raíz, recorre el sub-árbol izquierdo y recorre el sub-árbol derecho. PostOrden: Recorre el sub-árbol izquierdo, recurre el sub-árbol derecho y visita el nodo raíz.
Hola 😄, si quieren probar el código les comparto lo siguiente:
.
profundidad.js:
const arbol = {
valor: 25,
izquierda: {
valor: 10,
izquierda: {
valor: 8,
izquierda: {
valor: 6,
izquierda: {
valor: 1,
izquierda: null,
derecha: null,
},
derecha: {
valor: 7,
izquierda: null,
derecha: null,
},
},
derecha: null,
},
derecha: {
valor: 13,
izquierda: null,
derecha: {
valor: 15,
izquierda: null,
derecha: null,
},
},
},
derecha: {
valor: 40,
izquierda: {
valor: 30,
izquierda: {
valor: 26,
izquierda: null,
derecha: null,
},
derecha: null,
},
derecha: {
valor: 42,
izquierda: null,
derecha: {
valor: 49,
izquierda: {
valor: 45,
izquierda: null,
derecha: null,
},
derecha: {
valor: 51,
izquierda: null,
derecha: null,
},
},
},
},
};
const profundidadMin = function (raiz) {
if (!raiz) {
return 0;
}
var izquierda = profundidadMin(raiz.izquierda);
var derecha = profundidadMin(raiz.derecha);
if (!izquierda) {
return derecha + 1;
}
if (!derecha) {
return izquierda + 1;
}
return Math.min(izquierda, derecha) + 1;
};
let profundidadMinima = profundidadMin(arbol);
console.log("La profundidad mínima del árbol es: ", profundidadMinima);
const profundidadMax = function (raiz) {
if (!raiz) {
return 0;
}
var izquierda = profundidadMax(raiz.izquierda);
var derecha = profundidadMax(raiz.derecha);
if (!izquierda) {
return derecha + 1;
}
if (!derecha) {
return izquierda + 1;
}
return Math.max(izquierda, derecha) + 1;
};
let profundidadMaxima = profundidadMax(arbol);
console.log("La profundidad máxima del árbol es: ", profundidadMaxima);
.
Output:
Por si desean afianzar más los recorridos de los árboles:
https://platzi.com/clases/1319-discretas/12233-recorrido-de-arboles/
# Función para realizar DFS en un grafo dado
lista = []
def dfs(graph, node, visited, nivel):
# Marcar el nodo actual como visitado
visited[node] = True
print("Visitando nodo:", node)
# Recorrer todos los nodos adyacentes al nodo actual
for neighbor in graph[node]:
if not visited[neighbor]:
# Si el vecino no ha sido visitado, realizar DFS en él
dfs(graph, neighbor, visited, nivel +1)
lista.append(nivel)
return False
# Ejemplo de uso
if __name__ == "__main__":
# Grafo representado como listas de adyacencia
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1,6],
5: [2],
6:[4,7],
7:[6,8],
8:[7]
}
# Inicializar un arreglo para llevar un seguimiento de los nodos visitados
visited = [False] * len(graph)
print(len(graph))
# Realizar DFS desde el nodo 0
dfs(graph, 0, visited,1)
print(lista)
print(max(lista))
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?
o inicia sesión.