Basic Tree Data Structure

[Justin To]

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!

 

[Justin To]

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

 

[Dustin Barker]

Hi Justin,

The second 3 is the second iteration of the parent's child_nodes.each
- try replacing:

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

 

[Justin To]

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!

 

[Dustin Barker]

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 # (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

 

[Justin To]

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!

 

[Dustin Barker]

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?

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

 

[Dustin Barker]

Reposting - forgot to send as plain text and the message was
illegible! ;-)

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?

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

 

[Justin To]

Your illustration definetely helps. I guess my ultimate confusion comes
from the last two yields to e:

1. yield e # node b got e='c', so yielding #yielding to t.teach?
2. 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! =)

 

[Dustin Barker]

Your illustration definetely helps. I guess my ultimate confusion
comes
from the last two yields to e:


1. yield e # node b got e='c', so yielding #yielding to t.teach?
2. 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

 

[Justin To]

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

Thanks a bunch Dustin!

 

[Justin To]

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!!

 

[Dustin Barker]

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

 

[Glen Holcomb]

[Note: parts of this message were removed to make it a legal post.]

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

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


On Jun 11, 2008, at 5:08 PM, Justin To wrote:

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!!

You want to implement a depth first search. Poke around on google a bit and
you should find plenty of information.