Looping through a tree from trunk to leaves


#1

I’ve just built a acts_as_tree model,
now I need to render it out as a tree structure in view.
and I also need a action method to loop through every row of the
database following the tree structure ( from root to it’s branch, then
to the ends of the branch, then go back for other branches…). I think
both the view helper and action method need to use a similar loop style,
and this code may be popular, at lease useful. Is there any article
about this subject?

I’ve get a view snip, btw:
http://snippets.dzone.com/tag/acts_as_tree


#2

Nanyang Z. wrote:

http://snippets.dzone.com/tag/acts_as_tree

You might want to tell the Rails folk, too.
http://www.rubyonrails.com/community


Phillip “CynicalRyan” Gawlowski
http://cynicalryan.110mb.com/
http://clothred.rubyforge.org

Rule of Open-Source Programming #8:

Open-Source is not a panacea.


#3

At 3:45 AM +0900 4/21/07, Nanyang Z. wrote:

I’ve just built a acts_as_tree model,
now I need to render it out as a tree structure in view.
and I also need a action method to loop through every row …

The word “loop” may be leading you in the wrong direction. If
you hear the words “tree” or “hierarchy”, you should be looking
at recursive solutions. So, in pseudo-ruby:

walk - level is either an item or a tree of items

def walk(level)
if level.is_leaf?
# handle leaf action
else
# handle branch pre-action
level.each { |item| walk(item) }
# handle branch post-action
end
end

In my (limited) experience, recursive code tends to be very
small and simple, once written. Writing it, however, can be
challenging, in that it requires a different way of thinking
than iterative code does.

There are also tree-walk routines that will simply allow you
to iterate through the nodes of a tree. Whether there is a
routine such as this for your particular tree, I don’t know.

-r

http://www.cfcl.com/rdm Rich M.
http://www.cfcl.com/rdm/resume removed_email_address@domain.invalid
http://www.cfcl.com/rdm/weblog +1 650-873-7841

Technical editing and writing, programming, and web development


#4

On Apr 20, 11:45 am, Nanyang Z. removed_email_address@domain.invalid wrote:


Posted viahttp://www.ruby-forum.com/.

google thru rails-talk for ajax tree control, widgets, etc, you’ll
see:

http://ajaxonrails.wordpress.com/2006/11/26/ajaxonrailsdragdroptree/
http://www.epiphyte.ca/code/live_tree.html

and lots more


#5

Suraj K. wrote:

Nanyang Z. wrote:
This is a Depth First Search (DFS) tree traversal:

http://en.wikipedia.org/wiki/Depth-first_search

Way to go!!!


#6

Nanyang Z. wrote:

from root to it’s branch,
then to the ends of the branch,
then go back for other branches…

This is a Depth First Search (DFS) tree traversal:

http://en.wikipedia.org/wiki/Depth-first_search


#7

This will do for ‘MyModel’:

def view(args)
args[:children].each do |child|
printf("%03d %s%s\n", child.id, args[:level], child.class.name)
view(:children => child.children, :level =>
“#{args[:level].gsub(/./, ’ ')} …”)
end
end

view(:children => MyModel.find(:all, :conditions => [ “parent_id IS
NULL” ]), :level => ‘’)

Julian I. Kamil removed_email_address@domain.invalid


#8

Rich M. wrote:

The word “loop” may be leading you in the wrong direction. If
you hear the words “tree” or “hierarchy”, you should be looking
at recursive solutions.

Now it seems obviously “loop” IS a wrong word. Both “walk” and “travel”
are far more fit the idea.

I’ll start form a very simple tree, no cross. and your code certainly
give my a idea to start. thanks.

Suraj K. wrote:

This is a Depth First Search (DFS) tree traversal:

http://en.wikipedia.org/wiki/Depth-first_search

And thank you, Suraj K… The link and the terms no only help solve
my problem, but also open a world of search relate algorithm to me.