Arbres binaires équivalents

Il peut y avoir de nombreux arbres binaires différents contenant la même séquence de valeurs. Par exemple, voici deux arbres binaires stockant la séquence 1, 1, 2, 3, 5, 8, 13.

Dans la plupart des langages, il est assez complexe d’écrire une fonction permettant de vérifier si deux arbres binaires stockent la même séquence. Nous utilisons la concurrence et les canaux de Go pour écrire une solution simple et élégante.

Cet exemple utilise le package tree, qui définit le type :

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

Dans le code ci-dessous :

package main

import "golang.org/x/tour/tree"

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int)

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool

func main() {
}

Implémentez la fonction Walk
Testez la fonction Walk
- La fonction tree.New(k) construit un arbre binaire structuré de manière aléatoire (mais toujours trié) contenant les valeurs \(k\), \(2k\), \(3k\), …, \(10k\).
- Créez un nouveau canal ch et lancez le walker :
```
go Walk(tree.New(1), ch)
```
- Ensuite, lisez et imprimez 10 valeurs à partir du canal. Il devrait s’agir des nombres \(1\), \(2\), \(3\), …, \(10\).
Implémentez la fonction Same en utilisant Walk pour déterminer si les arbres t1 et t2 stockent les mêmes valeurs
Testez la fonction Same
- Same(tree.New(1), tree.New(1)) devrait retourner true, et Same(tree.New(1), tree.New(2)) devrait retourner false.
- La documentation de Tree se trouve ici.