Basic Tree Data Structure

Discussion in 'Ruby' started by Justin To, Jun 10, 2008.

  1. Justin To

    Justin To Guest

    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/.
    Justin To, Jun 10, 2008
    #1
    1. Advertising

  2. Justin To

    Justin To Guest

    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/.
    Justin To, Jun 10, 2008
    #2
    1. Advertising

  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/.
    >
    Dustin Barker, Jun 10, 2008
    #3
  4. Justin To

    Justin To Guest

    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/.
    Justin To, Jun 10, 2008
    #4
  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/.
    >
    Dustin Barker, Jun 10, 2008
    #5
  6. Justin To

    Justin To Guest

    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/.
    Justin To, Jun 10, 2008
    #6
  7. On Jun 10, 2008, at 4:58 PM, Justin To wrote:

    > 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, Jun 10, 2008
    #7
  8. Reposting - forgot to send as plain text and the message was
    illegible! ;-)

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

    > 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, Jun 10, 2008
    #8
  9. Justin To

    Justin To Guest

    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/.
    Justin To, Jun 10, 2008
    #9
  10. 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:
    >
    >
    > 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
    Dustin Barker, Jun 11, 2008
    #10
  11. Justin To

    Justin To Guest

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

    Thanks a bunch Dustin!
    --
    Posted via http://www.ruby-forum.com/.
    Justin To, Jun 11, 2008
    #11
  12. Justin To

    Justin To Guest

    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/.
    Justin To, Jun 11, 2008
    #12
  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/.
    >
    Dustin Barker, Jun 12, 2008
    #13
  14. Justin To

    Glen Holcomb Guest

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

    On Thu, Jun 12, 2008 at 8:00 AM, Dustin Barker <
    > 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/.
    >>
    >>

    >
    >

    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)
    Glen Holcomb, Jun 12, 2008
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,094
  2. sharan
    Replies:
    4
    Views:
    675
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    822
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    679
    CBFalconer
    Oct 30, 2007
  5. anne001
    Replies:
    1
    Views:
    228
Loading...

Share This Page