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)