class Tree

attr_reader :value

def initialize(value)

@value = value

@children = []

end

def <<(value)

subtree = Tree.new(value)

@children << subtree

return subtree

end

end

t = Tree.new(“Parent”)

child1 = t << “Child 1”

child2 = t << “Child 2”

child2 << “Grandchild 2.1”

ggc1 = child1 << “Grandchild 1.1”

ggc1 << “Great Grand Child 1.1.1”

ggc2 = child1 << “Grandchild 1.2”

ggc2 << “Great Grand Child 1.2.1”

class Tree

def each

yield value

@children.each do |child_node|

child_node.each { |e| yield e } # mainly confuesd at this point

end

end

end

t.each { |x| puts x }

Hi, I’m a little confused about the algorithm used to display each item

in a tree…

at: child_node.each { |e| yield e }

when does the block { |e| yield e } come into play? Does the each method

for child_node occur first?

Thanks in advance!

class Tree

attr_reader :value

def initialize(value)

@value = value

@children = []

end

def <<(value)

subtree = Tree.new(value)

@children << subtree

return subtree

end

end

t = Tree.new(“Parent”)

child1 = t << “Child 1”

child2 = t << “Child 2”

gc1 = child1 << “GC 1.1”

class Tree

def each

puts “1”

yield value

puts “2”

@children.each do |child_node|

puts “in child_node”

child_node.each { |e| puts “3”; yield e; }

end

end

end

t.each { |x| puts “t.each”; puts x }

OUTPUT:

1

t.each

Parent

2

in child_node

1

3

t.each

Child 1

2

in child_node

1

3 # why are there two 3’s here??

3 # ??? Doesn’t Child 1 only have one child in its array

@children??

t.each

GC 1.1

2

in child_node

1

3

t.each

Child 2

2

(^ comment)

Thanks in advance

Hi Justin,

The second 3 is the second iteration of the parent’s child_nodes.each

child_node.each { |e| puts “3”; yield e; }

with this:

child_node.each { |e| puts “3 #{value}”; yield e; }

to see which iteration belongs to which node.

-Dustin

Thanks Dustin, that clarifies one bit of the confusion, but I’m still

puzzled:

Output: Parent

in child node

3 Parent

Output: Child 1

in child node

3 Child 1

3 Parent # Q1: Why does it go through the Parent again?

Output: Grandchild 1.1

class Tree

def each

puts “1”

yield value # Q2: Which block does this invoke?

puts “2”

@children.each do |child_node|

puts “in child_node”

child_node.each { |e| puts “3”; yield e; } # Q3: Which block

does this

# yield invoke?

end

end

end

t.each { |x| puts “t.each”; puts x }

I’m trying hard to understand!! =D Thanks for the help!

Output:

each:a

each: node:a yields:b

each: node:a yields: node:b yields:c

each: node:a yields:d

Ok, from this example, I don’t know how the #{e} in “child_node.each {

|e| yield

“node:#{value} yields:#{e}” }” turns into “node:b yields:c” because the

#{e} isn’t calling yield is it?

Sorry for the trouble, I just can’t seem to understand…when I walk

through the algorithm with my logic it seems that it should just say

“each: node b yields c”…which is obviously not the correct output.

I’ll continue reviewing your example, though, but if you can explain in

any other way, that’d be great. Thanks again!

No problem - so try out this snippet:

t = Tree.new(“a”)

t1 = t << “b”

t1 << “c”

t << “d”

class Tree

def each

yield value

@children.each do |child_node|

child_node.each { |e| yield “node:#{value} yields:#{e}” }

end

end

end

t.each { |x| puts “each:#{x}” }

here’s some annotated output:

each:a # (a)

yield value

each:node:a yields:b # (b) yield value -

(a) yield e

each:node:a yields:node:b yields:c # © yield value -> (b) yield

e -> (a) yield e

each:node:a yields:d # (d) yield value -

(a) yield e

Seems like you’re traversing correctly, I think the 1,2,3 output

might’ve been confusing. The output of this snippet illustrates how

the calls stack up - each yield returns to the caller, which in turn

yields to it’s caller, and so on.

-Dustin

On Jun 10, 2008, at 4:58 PM, Justin To wrote:

#{e} isn’t calling yield is it?

That’s right, the e doesn’t call yield - the ‘each’ in child_node.each

does. Remember that you’re calling Tree#each here, so the value of ‘e’

is whatever is yielded by the ‘each’ method. You’ll have as many e’s

as you have yields.

Sorry for the trouble, I just can’t seem to understand…when I walk

through the algorithm with my logic it seems that it should just say

“each: node b yields c”…which is obviously not the correct output.

So if remove the debug statements:

class Tree

def each

yield value

@children.each do |child_node|

child_node.each { |e| yield e }

end

end

end

t.each { |x| puts x }

I get:

a

b

c

d

Is that the iteration you’re looking for? If so - let’s walk through it:

t.each

– yield value # node a is

yielding ‘a’ to t.each

puts x #

t.each outputs ‘a’

– @children.each do |child_node| # iterating children of node a

---- child_node.each # calling

Tree#each for first child of a, which is node b

------ yield value # node b is

yielding ‘b’

---- yield e # node a

got e=‘b’, so yielding ‘b’ to t.each

puts x #

t.each outputs ‘b’

------ @children.each do |child_node| # iterating children of node b

-------- child_node.each # calling Tree#each

for first child of b, which is node c

---------- yield value # node c is

yielding ‘c’

------ yield e # node b

got e=‘c’, so yielding ‘c’ to node a

---- yield e # node

a got e=‘c’, so yielding ‘c’ to t.each

puts x #

outputs ‘c’

I’ll continue reviewing your example, though, but if you can explain

in

any other way, that’d be great. Thanks again!

No problem - it’s a tough topic, hopefully the illustration of the

calls above helps!

-Dustin

Reposting - forgot to send as plain text and the message was

illegible!

On Jun 10, 2008, at 4:58 PM, Justin To wrote:

#{e} isn’t calling yield is it?

That’s right, the e doesn’t call yield - the ‘each’ in child_node.each

does. Remember that you’re calling Tree#each here, so the value of ‘e’

is whatever is yielded by the ‘each’ method. You’ll have as many e’s

as you have yields.

Sorry for the trouble, I just can’t seem to understand…when I walk

through the algorithm with my logic it seems that it should just say

“each: node b yields c”…which is obviously not the correct output.

So if remove the debug statements:

class Tree

def each

yield value

@children.each do |child_node|

child_node.each { |e| yield e }

end

end

end

t.each { |x| puts x }

I get:

a

b

c

d

Is that the iteration you’re looking for? If so - let’s walk through it:

t.each

– yield value # node a is yielding ‘a’ to t.each

puts x # t.each outputs ‘a’

– @children.each do |child_node| # iterating children of node a

---- child_node.each # calling Tree#each for first

child of a, which is node b

------ yield value # node b is yielding ‘b’

---- yield e # node a got e=‘b’, so yielding

‘b’ to t.each

puts x # t.each outputs ‘b’

------ @children.each do |child_node| # iterating children of node b

-------- child_node.each # calling Tree#each for first

child of b, which is node c

---------- yield value # node c is yielding ‘c’

------ yield e # node b got e=‘c’, so yielding

‘c’ to node a

---- yield e # node a got e=‘c’, so yielding

‘c’ to t.each

puts x # outputs ‘c’

I’ll continue reviewing your example, though, but if you can explain

in

any other way, that’d be great. Thanks again!

No problem - it’s a tough topic, hopefully the illustration of the

calls above helps!

-Dustin

On Jun 10, 2008, at 6:16 PM, Justin To wrote:

Your illustration definetely helps. I guess my ultimate confusion

comes

from the last two yields to e:

- yield e # node b got e=‘c’, so yielding #yielding to t.teach?
- yield e # node a got e=‘c’, so yielding

---------- yield value # node c is yielding ‘c’

------ yield e # node b got e=‘c’, so yielding ‘c’ to node a

---- yield e # node a got e=‘c’, so yielding ‘c’ to t.each

For #1, e=‘c’ so why doesn’t it yield that ‘c’ to t.each and puts ‘c’

It does, but by way of node b and node a. So let’s try with different

code:

def foo

bar { |x| yield “foo #{x}” }

end

def bar

baz { |x| yield “bar #{x}” }

end

def baz

yield “baz”

end

foo { |x| puts x }

output: foo bar baz

You’ve helped a lot and done all you could. It’ll just be up to me to

try to wrap my mind around it.

No problem - good luck!

-Dustin

GREAT!! That new example demystified the whole problem for me! Finally!!

=D

Thanks a bunch Dustin!

How would I traverse only one portion of the tree? For instance, only

Child 1 and not Child 2?

So I want to see:

=> “Child 1”

=> “Grandchild 1.1”

=> “Great Grand Child 1.1.1”

=> “Grandchild 1.2”

=> “Great Grand Child 1.2.1”

Thanks!!

Hi Justin,

If the tree is ordered, you could provide access the nth node by

implementing the [] operator. So for Child 1, could be:

subtree = tree[0]

subtree.each { |x| put x }

-Dustin

Your illustration definetely helps. I guess my ultimate confusion comes

from the last two yields to e:

- yield e # node b got e=‘c’, so yielding #yielding to t.teach?
- yield e # node a got e=‘c’, so yielding

For #1, e=‘c’ so why doesn’t it yield that ‘c’ to t.each and puts ‘c’

You’ve helped a lot and done all you could. It’ll just be up to me to

try to wrap my mind around it.

Thanks for the extended help…will definitely post back when I figure

it out! =)

On Thu, Jun 12, 2008 at 8:00 AM, Dustin Barker <

[email protected]> wrote:

=> “Grandchild 1.2”

=> “Great Grand Child 1.2.1”

## Thanks!!

Posted via http://www.ruby-forum.com/.

You want to implement a depth first search. Poke around on google a bit

and

you should find plenty of information.

–

“Hey brother Christian with your high and mighty errand, Your actions

speak

so loud, I can’t hear a word you’re saying.”

-Greg Graffin (Bad Religion)