golang implémente la traversée des précommandes

Le parcours de précommande est un type de parcours d'arbre binaire. L'ordre de parcours consiste à parcourir d'abord le nœud racine, puis à parcourir le sous-arbre de gauche et enfin à parcourir le sous-arbre de droite. Dans Golang, des algorithmes récursifs peuvent être utilisés pour implémenter le parcours de précommande.

Tout d'abord, nous devons définir la structure du nœud de l'arbre binaire, y compris la valeur du nœud, les pointeurs du sous-arbre gauche et du sous-arbre droit.

type Node struct {
        Value int
        Left  *Node
        Right *Node
}

Ensuite, nous pouvons définir une fonction récursivePreOrder pour effectuer un parcours de précommande.

func PreOrder(root *Node) []int {
        if root == nil {
                return []int{}
        }
        result := make([]int, 0)
        result = append(result, root.Value)
        result = append(result, PreOrder(root.Left)...)
        result = append(result, PreOrder(root.Right)...)
        return result
}

Dans la fonction, nous déterminons d'abord si le nœud racine est vide, et s'il est vide, renvoyons une tranche vide.

Sinon, nous ajoutons d'abord la valeur du nœud racine au résultat, puis appelons récursivement le sous-arbre gauche et le sous-arbre droit et les fusionnons dans le résultat.

Enfin, le résultat renvoyé est le résultat du parcours de précommande.

Vous trouverez ci-dessous un exemple de code complet.

package main

import "fmt"

type Node struct {
        Value int
        Left  *Node
        Right *Node
}

func PreOrder(root *Node) []int {
        if root == nil {
                return []int{}
        }
        result := make([]int, 0)
        result = append(result, root.Value)
        result = append(result, PreOrder(root.Left)...)
        result = append(result, PreOrder(root.Right)...)
        return result
}

func main() {
        root := &Node{
                Value: 1,
                Left: &Node{
                        Value: 2,
                        Left: &Node{
                                Value: 4,
                        },
                        Right: &Node{
                                Value: 5,
                        },
                },
                Right: &Node{
                        Value: 3,
                        Left: &Node{
                                Value: 6,
                        },
                        Right: &Node{
                                Value: 7,
                        },
                },
        }
        result := PreOrder(root)
        fmt.Println(result)
}

Le résultat de sortie est : [1 2 4 5 3 6 7], qui est le résultat du parcours pré-commandé de l'arbre binaire.

Grâce à l'algorithme récursif, il est très simple d'implémenter la traversée de pré-commande d'arbre binaire dans Golang et ne nécessite que quelques lignes de code pour être complété.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!