problem traversing a tree

[Uwe Schmitt]

Hello,

I'm new to ruby and I tried to implement a simple Tree
class, including tree traversal. The code is:


class Tree

def initialize(id, children)
@id = id
@children = children
end

def traverse_one
puts @id
@children.each do |subtree|
subtree.traverse_one
end
end

def traverse_iter
yield @id
@children.each do |subtree|
subtree.traverse_iter
end
end


end

three = Tree.new(3, [])
four = Tree.new(4, [])
two = Tree.new(2, [three,four])
one = Tree.new(1, [])
root = Tree.new(0,[one, two])

# works fine
root.traverse_one

# raises LocalJumError
root.traverse_iter{ |x| puts x }

As I commented Tree#traverse_one works fine, but Tree#traverse_iter
yields a LocalJumpError.

Any hints ?

Greetings, Uwe.

 

[ako...]

i think it has something to do with passing the block on to the inner
traverse_iter.

konstantin

 

[Dale Martenson]

If you change the traverse_iter function to explicitly reference the
block you can pass the block on as part of the recursive function call.

def traverse_iter( &block )
yield @id # or block.call(@id)
@children.each do |subtree|
subtree.traverse_iter( &block )
end
end

 

[Robert Klemme]

Hello,

I'm new to ruby and I tried to implement a simple Tree
class, including tree traversal. The code is:


class Tree

def initialize(id, children)
@id = id
@children = children
end

def traverse_one
puts @id
@children.each do |subtree|
subtree.traverse_one
end
end

def traverse_iter
yield @id
@children.each do |subtree|
subtree.traverse_iter
end
end


end

three = Tree.new(3, [])
four = Tree.new(4, [])
two = Tree.new(2, [three,four])
one = Tree.new(1, [])
root = Tree.new(0,[one, two])

# works fine
root.traverse_one

# raises LocalJumError
root.traverse_iter{ |x| puts x }

As I commented Tree#traverse_one works fine, but Tree#traverse_iter
yields a LocalJumpError.

Any hints ?

I think you got hints regarding your problem already. I'd just like to
additionally mention two things about your design: first, as you did it
"TreeNode" would be a more appropriate name for your class because that's
what it basically is. Second, tree implementations often use at least two
distinct classes - one for tree nodes and one for the tree as a whole.
That way you can better separate concerns (for example, store the size of
the tree, or have algorithms in place that make only sense for a complete
tree). It may not be necessary for your application - just wanted to
mention it.

Kind regards

robert

 

[Uwe Schmitt]

||=20
||=20
|| I think you got hints regarding your problem already. I'd=20
|| just like to
|| additionally mention two things about your design: first, as=20
|| you did it
|| "TreeNode" would be a more appropriate name for your class=20
|| because that's
|| what it basically is. Second, tree implementations often=20
|| use at least two
|| distinct classes - one for tree nodes and one for the tree=20
|| as a whole.
|| That way you can better separate concerns (for example,=20
|| store the size of
|| the tree, or have algorithms in place that make only sense=20
|| for a complete
|| tree). It may not be necessary for your application - just wanted to
|| mention it.

I'd like to thank for all contributions. Passing the block to the
recursive call works fine.

In reality I allready use two classes for representing the tree and
nodes. Here I just constructed a small example for provoking the
error message. Posting the full code would have lengthen my posting
too much.

Greetings, Uwe.