保存深度优先搜索的痕迹

Question

我在一个有树形结构的网页上搜索一些数据。你知道吗

网页包含类别，每个类别可以包含另一个类别，也可以是一个叶子（它包含特定的数据）。你知道吗

所以最简单的方法可能是使用递归在这个结构中进行搜索。但是我想把每片叶子找到后留下的痕迹保存起来。你知道吗

下面是一个例子：

url_of_1st_level_cat -> url_of_2nd_level_cat -> url_of_3rd_level_cat -> leaf 

我希望在处理这片叶子的时候能够得到叶子的整个痕迹。你知道吗

所以当我得到一些叶子时，我可以做，例如find_trace(leaf)，它返回：

[url_of_1st_level_cat,url_of_2nd_level_cat,url_of_3rd_level_cat]

下面是递归函数的伪代码，该函数正在搜索leaf：

def find_leafs_of_category(self,url):


   subcategories = self.get_subcategories(url)
   for subcategory in subcategories:
        if is_leaf(subcategory):
            # DO STUFF

        else: self.find_leafs_of_category(subcategory)

你对这个问题有什么好的简单的解决办法吗？你知道吗

编辑：应该对树进行排序，这样当出现问题时，它可以从结束处继续。你知道吗

更详细：

（AAC、AAB不是类别的实名，不能通过拆分实名来追踪）

A - AA ...
  - AB ...
  - AC - ACA ...
       - ACB ...
       - ACC ...
       - ACD - leaf1
             - leaf2
          - leaf3
          ...

1. 我使用方法find_leafs_of_category(A)
2. 现在，我想用这些叶子做些事情。所以它处理leaf,leaf,leaf...leaf1,leaf2，突然连接中断了。为了能够继续，我必须记住它已经处理了A - AA ...，A - AB...A - AC - ACA ...，A - AC - ACB ...，A-AC-ACC的所有叶子。。。从A - AC - ACD开始，经过处理的叶子是leaf1和leaf2。。。所以它必须能够得到跟踪，即A - AC - ACD - leaf3，并从这一点继续。你知道吗

Answer 1

我想到了一个可能的解决办法。 它实际上是伪代码，所以它不会“按原样”工作，但我认为你可以从中得到灵感！你知道吗

class Leafer(object):
    start_url = str
    last_visited_url = str
    leafs = []

    def find_leafs(self, url, subcategories=[]):
        self.last_visited_url = url
        new_sub = url.get_subcategories()
        for sub in new_sub:
            if is_leaf(url):
                self.leafs.append(Leaf(subcategories))
            else:
                self.find_leafs(sub, subcategories.append_sub)

class Leaf(object):
    subcategories = []

是不是可以用的？你知道吗

Answer 2

只需将这些元素的一个元组传递给递归调用，在下一个级别中，只需在传递时将当前级别添加到元组中。像这样：

def find_leafs_of_category(self, url, path):
    subcategories = self.get_subcategories(url)
    for subcategory in subcategories:
        if is_leaf(subcategory):
            # DO STUFF

        else:
            next_path = path + (url,)
            self.find_leafs_of_category(subcategory, next_path)

当然，您必须在第一次调用中传递一个空元组，或者，将参数的默认值设置为None，然后选中它来初始化它：

def find_leafs_of_category(self, url, path = None):
    if path is None:
        path = (,) # empty tuple