binarytrees.go

     1  // Copyright 2012 The Go Authors.  All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // +build ignore
     6  
     7  package main
     8  
     9  import (
    10  	"fmt"
    11  
    12  	"golang.org/x/tour/tree"
    13  )
    14  
    15  func walkImpl(t *tree.Tree, ch chan int) {
    16  	if t == nil {
    17  		return
    18  	}
    19  	walkImpl(t.Left, ch)
    20  	ch <- t.Value
    21  	walkImpl(t.Right, ch)
    22  }
    23  
    24  // Walk walks the tree t sending all values
    25  // from the tree to the channel ch.
    26  func Walk(t *tree.Tree, ch chan int) {
    27  	walkImpl(t, ch)
    28  	// Need to close the channel here
    29  	close(ch)
    30  }
    31  
    32  // Same determines whether the trees
    33  // t1 and t2 contain the same values.
    34  // NOTE: The implementation leaks goroutines when trees are different.
    35  // See binarytrees_quit.go for a better solution.
    36  func Same(t1, t2 *tree.Tree) bool {
    37  	w1, w2 := make(chan int), make(chan int)
    38  
    39  	go Walk(t1, w1)
    40  	go Walk(t2, w2)
    41  
    42  	for {
    43  		v1, ok1 := <-w1
    44  		v2, ok2 := <-w2
    45  		if !ok1 || !ok2 {
    46  			return ok1 == ok2
    47  		}
    48  		if v1 != v2 {
    49  			return false
    50  		}
    51  	}
    52  }
    53  
    54  func main() {
    55  	fmt.Print("tree.New(1) == tree.New(1): ")
    56  	if Same(tree.New(1), tree.New(1)) {
    57  		fmt.Println("PASSED")
    58  	} else {
    59  		fmt.Println("FAILED")
    60  	}
    61  
    62  	fmt.Print("tree.New(1) != tree.New(2): ")
    63  	if !Same(tree.New(1), tree.New(2)) {
    64  		fmt.Println("PASSED")
    65  	} else {
    66  		fmt.Println("FAILED")
    67  	}
    68  }
    69
View as plain text