Comment implémenter un programme Golang qui retourne un arbre binaire

Flip Binary Tree golang

Le retournement de l'arbre binaire est une question d'algorithme classique et est souvent posée lors des entretiens. Dans cet article, nous allons implémenter un programme Golang qui retourne un arbre binaire.

Qu'est-ce qu'un arbre binaire

Un arbre binaire est une structure arborescente composée d'un ensemble limité de nœuds, y compris un nœud racine, et chaque nœud est connecté respectivement aux nœuds enfants gauche et droit. Lorsque tous les nœuds n’ont pas de nœuds enfants gauche ou droit, la structure arborescente est appelée arbre binaire.

En golang, les structures sont souvent utilisées pour représenter les nœuds d'arbres binaires. Par exemple :

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

Nous utilisons le code ci-dessus pour définir un nœud d'arbre binaire, où Val représente la valeur du nœud, Left représente le nœud enfant gauche et Right représente le nœud enfant droit .

Comment retourner un arbre binaire

Le problème du retournement d'un arbre binaire semble simple, mais il implique en réalité des problèmes complexes. Pour faciliter l'explication, nous supposons qu'il existe un arbre binaire comme suit :

4
/
2 7

 / \
6   9

Après le retournement, l'arbre binaire devrait devenir :

 4

/
7 2
/
9 6

En termes d'implémentation de code, nous pouvons utiliser des méthodes récursives pour résoudre ce problème. La méthode récursive peut utiliser directement le pointeur de la structure pour échanger les positions des nœuds enfants gauche et droit. Le code de la méthode récursive est le suivant :

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root

}

Nous avons déclaré une fonction nommée invertTree, qui reçoit le pointeur du nœud racine d'un arbre binaire en paramètre et renvoie un pointeur transmis vers le nouvel arbre binaire qui est inversé. Si le nœud racine est vide, nil est renvoyé.

À l'intérieur du corps de la fonction, nous utilisons la récursion pour terminer le processus de retournement de l'arbre binaire. Nous échangeons le nœud enfant gauche et le nœud enfant droit du nœud racine, puis appliquons ce processus de manière récursive aux nœuds enfants.

Enfin, nous renvoyons le pointeur du nœud racine du nouvel arbre binaire inversé.

Le code complet est le suivant :

package main

import "fmt"

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root

}

f unc principal () {

root := &TreeNode{Val: 4, Left: &TreeNode{Val: 2},
    Right: &TreeNode{Val: 7, Left: &TreeNode{Val: 6}, 
           Right: &TreeNode{Val: 9}}}

fmt.Println("Before invert: ")
fmt.Println(root.Val, root.Left.Val, root.Right.Val, root.Right.Left.Val, root.Right.Right.Val)

invertTree(root)

fmt.Println("After invert: ")
fmt.Println(root.Val, root.Left.Val, root.Right.Val, root.Left.Left.Val, root.Left.Right.Val)

}

Dans cet exemple, nous définissons d'abord le nœud racine d'un arbre binaire. Dans la fonction principale, nous appelons la fonction invertTree pour inverser l'arbre binaire. Enfin, nous imprimons l'arbre binaire avant et après le retournement.

Conclusion

Dans cet article, nous avons montré un programme Golang sur la façon de retourner un arbre binaire. En utilisant une simple fonction récursive, notre programme peut très bien résoudre ce problème. J'espère que cet article aidera tout le monde à comprendre le problème du retournement de l'arbre binaire et de l'utilisation du langage Golang.

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!