Created
September 15, 2013 06:21
-
-
Save pixyj/6568459 to your computer and use it in GitHub Desktop.
Equivalent binary trees in Go Solution to http://tour.golang.org/#70
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
// Copyright 2011 The Go Authors. All rights reserved. | |
// Use of this source code is governed by a BSD-style | |
// license that can be found in the LICENSE file. | |
package main | |
import ( | |
"fmt" | |
"math/rand" | |
) | |
// A Tree is a binary tree with integer values. | |
type Tree struct { | |
Left *Tree | |
Value int | |
Right *Tree | |
} | |
// 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 | |
} | |
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 | |
} | |
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 (t *Tree) Walk() string { | |
s := "" | |
if t.Left != nil { | |
s += t.Left.Walk() | |
} | |
s += fmt.Sprintf("%d", t.Value) | |
if t.Right != nil { | |
s += t.Right.Walk() | |
} | |
return s | |
} | |
func (t *Tree) WalkChan(c chan string) { | |
s := t.Walk() | |
c <- s | |
} | |
func Same(t1, t2 *Tree) bool { | |
c := make(chan string) | |
go t1.WalkChan(c) | |
go t2.WalkChan(c) | |
one, two := <-c, <-c | |
return one == two | |
} | |
func main() { | |
one := New(100) | |
two := New(100) | |
three := New(100) | |
four := New(200) | |
fmt.Println(Same(three, four)) | |
fmt.Println(Same(one, two)) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment