Basic Tree Data Structure

ruby-talk
1

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!

···

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

2

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

···

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

3

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

···

On Jun 10, 2008, at 1:46 PM, Justin To wrote:

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
--
Posted via http://www.ruby-forum.com/\.

4

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!

···

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

5

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

···

On Jun 10, 2008, at 3:04 PM, Justin To wrote:

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!
--
Posted via http://www.ruby-forum.com/\.

6

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!

···

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

7

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

···

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

8

Reposting - forgot to send as plain text and the message was illegible! :wink:

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

···

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

9

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

···

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

10

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

···

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

11

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

Thanks a bunch Dustin!

···

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

12

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

···

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

13

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!!
--
Posted via http://www.ruby-forum.com/\.

14

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

···

On Thu, Jun 12, 2008 at 8:00 AM, Dustin Barker < dustin.barker@agilepartners.com> wrote:

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!!
--
Posted via http://www.ruby-forum.com/\.

--
"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)