Introducción

1

¿Qué es un grafo?

2

¿Qué es un árbol?

3

¿Qué es recursión?

4

Aplicaciones reales de grafos y árboles

5

Formas de representar un grafo

DFS

6

Análisis de DFS: algoritmo de búsqueda en profundidad

7

Programando DFS de forma recursiva

8

Otras formas de programar DFS

9

Recorridos y profundidad de un Árbol

10

Sum Root to Leaf Numbers: análisis del problema

11

Solución de Sum Root to Leaf Numbers

12

Playground: Sum Root to Leaf Numbers

13

Programando Sum Root to Leaf Numbers en Golang

14

Number of Islands: análisis del problema

15

Solución de Number of Islands

16

Playground: Number of Islands

17

Programando Number of Islands en Python

18

Ejercicios recomendados de DFS

19

Ejercicios resueltos de DFS

BFS

20

Análisis de BFS: algoritmo de búsqueda en anchura

21

Programando BFS con Python

22

Minimum Knights Moves (movimientos de caballo en ajedrez): análisis del problema

23

Solución de Minimum Knights Moves

24

Playground: Minimum Knights Moves

25

Programando Minimum Knights Moves con Python

26

Rotting Oranges: análisis del problema

27

Solución de Rotting Oranges

28

Playground: Rotting Oranges

29

Rotting Oranges con Java

30

Shortest Bridge Between Islands: análisis del problema

31

Solución de Shortest Bridge Between Islands

32

Playground: Shortest Bridge Between Islands

33

Programando Shortest Bridge Between Islands con Python

34

Ejercicios recomendados de BFS

35

Ejercicios resueltos de BFS

Backtrack

36

Algoritmo de Backtrack

37

Letter Combinations of a Phone Number: análisis del problema

38

Solución de Letter Combinations of a Phone Number

39

Programando Letter Combinations of a Phone Number con C++

40

Playground: Letter Combinations of a Phone Number

41

Restore IP Addresses: análisis del problema

42

Programando Restore IP Addresses con C++

43

Playground: Restore IP Addresses

44

Word Search: análisis del problema

45

Solución de Word Search

46

Playgrund: Word Search

47

Programando Word Search JavaScript

48

Reto: N Queens Puzzle

49

Ejercicios recomendados de Backtrack

50

Ejercicios resueltos de Backtrack

Próximos pasos

51

¿Qué otros algoritmos y tipos de grafos puedes aprender?

52

¿Quieres más cursos avanzados de algoritmos?

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Aprovecha el precio especial y haz tu profesión a prueba de IA

Antes: $249

Currency
$209
Suscríbete

Termina en:

0 Días
2 Hrs
4 Min
57 Seg

Recorridos y profundidad de un Árbol

9/52
Recursos

¿Cómo recorrer un árbol binario?

Un árbol binario es una estructura de datos muy utilizada en disciplinas como la informática y la matemática. Comprender cómo recorrerlo es esencial para su manejo y aplicación en la solución de problemas complejos. En este aprendizaje, abordaremos tres tipos de recorridos de árboles: in order, preorder y postorder, que permiten visitar cada nodo del árbol en un orden específico.

¿Qué es el recorrido in order?

El recorrido in order se centra en recorrer primero el hijo izquierdo, luego el nodo actual, y finalmente el hijo derecho. Este método es indispensable para obtener los nodos de un árbol o subárbol de forma ordenada.

In order con un árbol binario:

def in_order(nodo):
    if nodo:
        in_order(nodo.izquierdo)
        print(nodo.valor)  # Mostrar o procesar el nodo actual
        in_order(nodo.derecho)

En este código, primero se llama a la función para el hijo izquierdo, luego se procesa el nodo actual, y finalmente se invade el hijo derecho.

¿Qué es el recorrido preorder?

Preorder inicia siempre en el nodo actual antes de pasar a sus hijos. Es especialmente útil en situaciones donde es crucial procesar el nodo antes de profundizar en él.

Preorder con un árbol binario:

def preorder(nodo):
    if nodo:
        print(nodo.valor)  # Mostrar o procesar el nodo actual
        preorder(nodo.izquierdo)
        preorder(nodo.derecho)

En el caso de árboles enearios, preorder consistiría en gestionar el nodo actual y después proceder con todos sus hijos, independientemente de si son más de dos.

¿Qué es el recorrido postorder?

Postorder, como su nombre indica, está diseñado para procesar el nodo al final, siendo los hijos el foco inicial del recorrido.

Postorder con un árbol binario:

def postorder(nodo):
    if nodo:
        postorder(nodo.izquierdo)
        postorder(nodo.derecho)
        print(nodo.valor)  # Mostrar o procesar el nodo actual

Este método es ideal para operaciones donde es obligatorio finalizar con la revisión de los hijos, como las evaluaciones aritméticas.

¿Cómo calcular la profundidad de un árbol?

La profundidad de un árbol, o la longitud máxima de un camino, puede ser un aspecto fundamental en la evaluación de su estructura. La profundidad máxima se determina partiendo desde la raíz hacia la hoja más lejana.

¿Cómo se implementa el cálculo recursivo de la profundidad?

El cálculo de la profundidad es frecuentemente implementado de forma recursiva. Aquí un ejemplo de código sobre cómo podría ejecutarse:

def profundidad(nodo):
    if nodo is None:
        return 0
    else:
        izquierda = profundidad(nodo.izquierdo)
        derecha = profundidad(nodo.derecho)
        return max(izquierda, derecha) + 1

Este algoritmo verifica el nodo izquierdo y derecho, evocando la misma función para calcular cuál de los caminos es el más largo, sumándole uno para incluir el nodo actual.

¿Cómo modificar el algoritmo para árboles enearios?

Cuando se trabaja con árboles enearios, es necesario iterar por todos los hijos en lugar de simplemente hacerlo con el hijo izquierdo y el derecho:

def profundidad_ene(nodo):
    if nodo is None:
        return 0
    else:
        max_profundidad = 0
        for hijo in nodo.hijos:
            max_profundidad = max(max_profundidad, profundidad_ene(hijo))
        return max_profundidad + 1

Este patrón tiene en cuenta cada uno de los hijos del nodo, asegurando que ninguno quede sin explorar.

Sigue practicando con estas técnicas para dominar la estructura y el recorrido de los árboles. ¡El futuro de tu aprendizaje en estructuras de datos es prometedor!

Aportes 9

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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:

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.

Por si desean afianzar más los recorridos de los árboles:

https://platzi.com/clases/1319-discretas/12233-recorrido-de-arboles/

Un ejemplo Practico de la vida Real de un Arobol es el Sistem de Direcotrios d Unix OS . donde el Nodo \[ Directorio ] Raiz es '/' y de ally se vienen todos los subDirectorios hijos del root. por tanto la ruta Absoluta para llegar a mi Directorio Algoritmos que esta en Directorio PAdre \[ PlayGround "es : / home / BryanLinuxUser / Documents / PlayGround / Algorithms / luego en la caprte algoritmos Yo tengo un text File : Fast\_and\_Slow\_Pointer.cpp que es un aricho dentro de my Directorio Algorithms que esta dentro de mi directorio PlayGround que esta en ~/Documents que esta en myUser que esta en / home . por eso es importante la REcursion en Grafos y Arboles , ps es lo mismo varias veces, ahora la profundidad de mi Archivo Fast\_Slow\_Pointers.cpp seria : 6 desde mi Nodeo\[Directorio] Raiz : root '/' , y es Genial ver el File System de ua computadora de esta forma , \n En Windows es lo mismo pero partiendo desde C: y dando '\\' como salto de Carpetas\[Folders] \n Cuando entiendas el Compceto de Arbol de Folders de tu computadora estaras en otro nivel de IT by FreddyVega en unos de sus PlatziVideos por ala en 2019\n
Este Codigo Recursivo me gusta ms \n . ```js function inorder(root) { if(root == null) return; inorder(root.left); document.write(root.key+" "); inorder(root.right); } ```function inorder(root) { if(root == null) return; inorder(root.left); document.write(root.key+" "); inorder(root.right); }
Qué bien explicado.
# 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))