如何通过自引用子主题进行递归搜索？

如果我有一个自我指涉的主题类，我想通过我所有的子主题的递归循环，这将是一个很好的Ruby的方式来做到这一点：如何通过自引用子主题进行递归搜索？

@category.topics.all(:parent_id => topic.id).each do |subtopic| 
    subtopic.delete_tags 
    @category.topics.all(:parent_id => subtopic.id).each do |subsubtopic| 
    subsubtopic.delete_tags 
     @category.topics.all(:parent_id => subsubtopic.id).each do |subsubsubtopic| 
     subsubtopic.delete_tags 
      @category.topics.all(:parent_id => subsubsubtopic.id).each do |subsubsubsubtopic| 
      subsubsubtopic.delete_tags 
      end 
     end 
    end 
end

来源

2009-09-14 janik

像这样的事情？

class Topic 
    def delete_subtopic_tags 
    all(:parent_id => self.id).each do |subtopic| 
     subtopic.delete_subtopic_tags 
     subtopic.delete_tags 
    end 
    end 
end

来源

2009-09-14 21:55:57

这会进入无限循环吗？ – jprete 2009-09-14 22:07:08

如果数据库中存在任何与'parent_id'相同的主题，那么它们会。 – rcoder 2009-09-14 22:10:18

@jprete：如果某个话题是自身的一个子话题，那它只会是无限的。但是这本身就像是一个错误。否则递归会在到达没有子主题的主题时结束。但它似乎应该是'：parent_id => self.id'。 – Chuck 2009-09-14 22:17:28

这是一个ActiveRecord模型类吗？如果是这样，你应该能够使用类似下面的代码通过子对象干净递归：

class Topic 
    has_many :topics 
    belongs_to :parent, :classname => "Topic", :foreign_key => 'parent_id' 

    # ...other model class logic... 
    def delete_tags_recursive 
    delete_tags 
    topics.each {|subtopic| subtopic.delete_tags_recursive } 
    end 
end

这有让您使用由has_many和belongs_to装饰，以创建topics和parent方法的额外好处轻松走过话题树。

来源

2009-09-14 21:57:18 rcoder

我不知道Ruby的，但如果你有哈希表和链接列表实现方便我会做这样的事情（在Java中上下的伪代码）：

Topic currentTopic = topic; 
list.add(currentTopic); 
hashtable.add(currentTopic); 
while (list.empty() == false) { 
    for (Topic t : currentTopic.getSubtopics()) { 
     if (hashtable.contains(t) == false) { 
      list.add(t); 
      hashtable.add(t); 
     } 
    } 
    visit(currentTopic); 
    list.remove(currentTopic); 
    currentTopic = list.getFirst(); 
}

这里的主要观点是保留散列表列表，以便您可以轻松确保您永远不会访问两次主题。除此之外，它实质上是breadth-first search的实现。 visit（）为每个单独的主题做你需要做的任何事情。

来源

2009-09-14 22:03:47 jprete

如何通过自引用子主题进行递归搜索？

回答

相关问题