Quels sont les méthodes pour parcourir différents arbres de données?

L'itinéraire des arbres de données est généralement effectué par les méthodes suivantes:

1. Parcours en profondeur (DFS)

   • Pré-ordre (racine → gauche → droit)
   • In-ordre (gauche → racine → droit)
   • Post-ordre (gauche → droit → racine)

2. Parcours en largeur (BFS)

   • Visite des nœuds par niveaux, en commençant par la racine

En Go, cela peut être implémenté de manière récursive ou à l'aide d'une pile/queue. Par exemple, parcours en profondeur (in-ordre) pour un arbre binaire:

func inOrder(node *Node) {
    if node == nil {
        return
    }
    inOrder(node.Left)
    fmt.Println(node.Value)
    inOrder(node.Right)
}

Pour le parcours en largeur, on utilise généralement une file d'attente:

func bfs(root *Node) {
    if root == nil {
        return
    }
    queue := []*Node{root}
    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        fmt.Println(current.Value)
        if current.Left != nil {
            queue = append(queue, current.Left)
        }
        if current.Right != nil {
            queue = append(queue, current.Right)
        }
    }
}