// inorder depth-first tree traversalfunc Walk(t *tree.Tree, ch chan int) {
if t.Left != nil {Walk(t.Left, ch)}ch <- t.Value // process nodeif t.Right != nil {Walk(t.Right, ch)}}
// walk the full tree, close output channel when donefunc FullWalk(t *tree.Tree, ch chan int) {Walk(t, ch)close(ch)}func Same(t1, t2 *tree.Tree) bool {ch1 := make(chan int)go FullWalk(t1, ch1)ch2 := make(chan int)
go FullWalk(t2, ch2)for {
Hello peoples,I'm working my way through the tour online, which I find an excellent idea, great way to learn, hands on!I wondered if I could solve the binary tree exercise so that it would handle trees of unknown size, and this is what I came up with, is there a cleaner way?Or more efficient?package mainimport ("fmt""tour/tree")
// inorder depth-first tree traversalfunc Walk(t *tree.Tree, ch chan int) {if t.Left != nil {Walk(t.Left, ch)}ch <- t.Value // process node
Also, I made an implementation a while back using only func values and thought it was neat. I have no idea how the performance compares:
Thanks Steven and Kyle for your suggestions. I like the idea of having the closure in Walk(), it minimizes the number of functions visible from the outside. And indeed, it seems better to first check if the node is not nil, before doing anything with it... Lastly, introducing a quit channel to stop any blocked goroutine will be a good way to avoid spilling recourses in a long running program. Are "lingering" goroutines like this the sources of what some refer to as go "memory leaks"?
Reply from off list:
On Oct 18, 2011, at 3:53 PM, Erwin <snes...@gmail.com> wrote:
> I understand. In this specific case, with the Walk(), what memory is exactly referenced? Just the single tree node that was given as the parameter? Or, because of the recursion, all the nodes that are used in the Walk() s that are being executed? I figure it's the latter case. Plus the channel?
The node, all it's descendants, the channel, and the goroutine's stack are all pinned by the goroutine.
I seem to recall a while ago hearing a proposal whereby if a goroutine is blocked on a channel, and contains the only remaining reference to that channel (e.g. all other references are gc'd), then the whole goroutine can be cleaned up because it can never continue. Was that suggestion rejected, or is it just something that hasn't been done yet? Granted, it's not a panacea; two goroutines that are deadlocked on each other would live forever because the channel is now referenced from to separate goroutines, and I don't think we need Go's runtime to try and do sophisticated inter-goroutine deadlock analysis.-Kevin