Python中的递归遍历分类树

Question

我是Python新手，知道有一种更好的方法来构造递归查询。希望有人更先进的看看如何最好地简化下面的代码。你知道吗

我在StackOverflow上列举了类似的例子，但是没有一个有我正在尝试遍历的数据结构。你知道吗

样本数据：

[
    {'categoryId': 100, 'parentId': 0,   'catName': 'Animals & Pet Supplies'},
    {'categoryId': 103, 'parentId': 100, 'catName': 'Pet Supplies'},
    {'categoryId': 106, 'parentId': 103, 'catName': 'Bird Supplies'},
    {'categoryId': 500, 'parentId': 0,   'catName': 'Apparel & Accessories'},
    {'categoryId': 533, 'parentId': 500, 'catName': 'Clothing'},
    {'categoryId': 535, 'parentId': 533, 'catName': 'Activewear'}
]

Python代码：

def returnChildren(categoryId):
    cats  = dict()
    results = categories.find( { "parentId" : categoryId } )
    for x in results:
        cats[x['categoryId']] = x['catName']

    return cats

children = returnChildren(cat_id)

#build list of children for this node
for x in children:
    print (x, "-", children[x])
    results = returnChildren(x)
    if (len(results) > 0):
        for y in sorted(results.keys()):
            print(y, "--", results[y])
            sub_results = returnChildren(y)
            if (len(sub_results) > 0):
            for z in sorted(sub_results.keys()):
                print(z, "----", sub_results[z])
                sub_sub_results = returnChildren(z)
                if (len(sub_sub_results) > 0):
                    for a in sorted(sub_sub_results.keys()):
                        print(a, "------", sub_sub_results[a])

此代码将生成一个类似于以下内容的树：

100 Animals & Pet Supplies
103 - Pet Supplies
106 -- Bird Supplies
500 Apparel & Accessories
533 - Clothing
535 -- Activewear

Answer 1

可以使用递归函数遍历树。你知道吗

此外，预先计算亲子关系树可能是值得的（它也可以用于其他目的）。你知道吗

我在这里把东西包装成一个类——应该很容易理解。你知道吗

（编辑：在早期版本中，我没有使用回调函数，而是改为使用生成器，更具python风格。）

from collections import defaultdict


class NodeTree:
    def __init__(self, nodes):
        self.nodes = nodes
        self.nodes_by_parent = defaultdict(list)

        for node in self.nodes:
            self.nodes_by_parent[node["parentId"]].append(node)

    def visit_node(self, node, level=0, parent=None):
        yield (level, node, parent)
        for child in self.nodes_by_parent.get(node["categoryId"], ()):
            yield from self.visit_node(child, level=level + 1, parent=node)

    def walk_tree(self):
        """
        Walk the tree starting from the root, returning 3-tuples (level, node, parent).
        """
        for node in self.root_nodes:
            yield from self.visit_node(node)

    @property
    def root_nodes(self):
        return self.nodes_by_parent.get(0, ())


nodes = [
    {"categoryId": 100, "parentId": 0, "catName": "Animals & Pet Supplies"},
    {"categoryId": 103, "parentId": 100, "catName": "Pet Supplies"},
    {"categoryId": 106, "parentId": 103, "catName": "Bird Supplies"},
    {"categoryId": 500, "parentId": 0, "catName": "Apparel & Accessories"},
    {"categoryId": 533, "parentId": 500, "catName": "Clothing"},
    {"categoryId": 535, "parentId": 533, "catName": "Activewear"},
]

tree = NodeTree(nodes)

for level, node, parent in tree.walk_tree():
    print(node["categoryId"], "-" * level, node["catName"])

这个代码打印出来，几乎和你原来的一样

100  Animals & Pet Supplies
103 - Pet Supplies
106   Bird Supplies
500  Apparel & Accessories
533 - Clothing
535   Activewear