Arbres binaires équivalents – avec solutions

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() {
}

1. Implémentez la fonction Walk
2. 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\).
3. Implémentez la fonction Same en utilisant Walk pour déterminer si les arbres t1 et t2 stockent les mêmes valeurs
4. 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.

Solution

package main

import (
    "fmt"

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

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

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    defer close(ch) // <- closes the channel when this function returns
    var walk func(t *tree.Tree)
    walk = func(t *tree.Tree) {
        if t == nil {
            return
        }
        walk(t.Left)
        ch <- t.Value
        walk(t.Right)
    }
    walk(t)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
    ch1 := make(chan int)
    ch2 := make(chan int)
    go Walk(t1, ch1)
    go Walk(t2, ch2)

    for {
        v1, ok1 := <-ch1
        v2, ok2 := <-ch2

        // return false if the values are different
        // or if one channel is closed and the other is not
        if v1 != v2 || ok1 != ok2 {
            return false
        }

        // return true if both channels are closed.
        // We just have to test one channel, because we
        // know that here, ok1 == ok2.
        if !ok1 {
            return true
        }
    }
}

func main() {
    ch := make(chan int)
    go func() {
        Walk(tree.New(1), ch)
    }()
    for v := range ch {
        fmt.Println(v)
    }

    fmt.Println(Same(tree.New(1), tree.New(1)))
    fmt.Println(Same(tree.New(1), tree.New(2)))

}