Last active
April 26, 2020 02:33
-
-
Save nem035/3bb639044866b49b5c6e195462b3cca2 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
"math/rand" | |
) | |
type Tree struct { | |
Left *Tree | |
Value int | |
Right *Tree | |
} | |
func (t *Tree) String() string { | |
if t == nil { | |
return "()" | |
} | |
s := "" | |
if t.Left != nil { | |
s += t.Left.String() + " " | |
} | |
s += fmt.Sprint(t.Value) | |
if t.Right != nil { | |
s += " " + t.Right.String() | |
} | |
return "(" + s + ")" | |
} | |
func insert(t *Tree, v int) *Tree { | |
if t == nil { | |
return &Tree{nil, v, nil} | |
} | |
if v < t.Value { | |
t.Left = insert(t.Left, v) | |
} else { | |
t.Right = insert(t.Right, v) | |
} | |
return t | |
} | |
// New returns a new, random binary tree holding the values k, 2k, ..., 10k. | |
func New(k int) *Tree { | |
var t *Tree | |
for _, v := range rand.Perm(10) { | |
t = insert(t, (1+v)*k) | |
} | |
return t | |
} | |
// Walk walks the tree t sending all values | |
// from the tree to the channel ch. | |
func Walk(t *Tree, ch chan int) { | |
recursiveWalk(t, ch) | |
close(ch) | |
} | |
func recursiveWalk(t *Tree, ch chan int) { | |
if t == nil { | |
return | |
} | |
recursiveWalk(t.Left, ch) | |
ch <- t.Value | |
recursiveWalk(t.Right, ch) | |
} | |
// Same determines whether the trees | |
// t1 and t2 contain the same values. | |
func Same(t1, t2 *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 | |
if ok1 != ok2 { | |
return false | |
} | |
if v1 != v2 { | |
return false | |
} | |
return true | |
} | |
} | |
func main() { | |
ch := make(chan int) | |
t1 := New(1) | |
go Walk(t1, ch) | |
fmt.Printf("t1 values: ") | |
for v := range ch { | |
fmt.Printf("%d ", v) | |
} | |
t2 := New(2) | |
fmt.Printf("\n\nis\n%s\nis equal to\n%s\n%v\n", t1, t1, Same(t1, t1)) | |
fmt.Printf("\nis\n%s\nis equal to\n%s\n%v\n\n", t1, t2, Same(t1, t2)) | |
} | |
// t1 values: 1 2 3 4 5 6 7 8 9 10 | |
// | |
// is | |
// ((((1 (2)) 3 (4)) 5 ((6) 7 ((8) 9))) 10) | |
// is equal to | |
// ((((1 (2)) 3 (4)) 5 ((6) 7 ((8) 9))) 10) | |
// true | |
// | |
// is | |
// ((((1 (2)) 3 (4)) 5 ((6) 7 ((8) 9))) 10) | |
// is equal to | |
// ((((2) 4 (6)) 8 (10 (12))) 14 ((16) 18 (20))) | |
// false |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment