The students of backend development must be impressed by the infinite classification, did they spend a lot of time at the beginning?

There are many application scenarios of infinite level classification tree structure. For example, back-end research and development needs to read out user permissions and generate a tree structure. Front-end research and development can display the columns that users have permissions to access according to the structure after getting the permission tree. Another example is the column classification on the web page:The author scratched his head when he first encountered the requirement of tree structure generation, and later found a generation algorithm with less code and clear understanding: recursion.

First, ensure that the following category information is stored in the database:

[{" id ": 1," name ": 'electronics'," parent ": 0}, {" id" : 2, "name" : "fruit", "parent" : 0}, {" id ": 3," name ":' household electrical appliances," parent ": 1}, {" id ": 4," name ":" hair dryer ", "parent" : 3}, {" id ": 5," name ":" fan ", "parent" : 3}, {" id ": 6," name ": 'desk lamp," parent ": 3}, {" id ": 7," name ": 'commercial electrical appliances," parent ": 1}, {" id" : 8, "name" :' large electric heat pan, "parent" : 7},]Copy the code

The parent field records the parent number of this item. For example, the parent number of a hairdryer is 3, indicating that the hairdryer is a household appliance. The parent number of a household appliance is 1, indicating that the household appliance is an electrical appliance. Hairdryer items are not directly associated with electrical items, but a tree structure is needed to show the relationship between electrical appliances <- household appliances <- hairdryer.

Copyright watermarking wechat public number Python programming reference

The operation of finding the parent number through parent and establishing the correlation relationship is actually repeated until all nodes are found, which is very similar to the recursive algorithm, and it is easy to write the corresponding recursive code:

def generate_tree(source, parent):
    tree = []
    for item in source:
        if item["parent"] == parent:
            item["child"] = generate_tree(source, item["id"])
            tree.append(item)
    return tree
Copy the code

You simply pass the information stored in the database to the generate_tree function. The recursive code loops back and forth looking for children through parent, and then adds them to the tree. The complete code is as follows:

import json def generate_tree(source, parent): tree = [] for item in source: if item["parent"] == parent: item["child"] = generate_tree(source, item["id"]) tree.append(item) return tree if __name__ == '__main__': Permission_source = [{" id ": 1," name ": 'electronics'," parent ": 0}, {" id" : 2, "name" : "fruit", "parent" : 0}, {" id ": 3," name ": 'household electrical appliances, "parent" : 1}, {" id ": 4," name ":' hair dryer," parent ": 2}, {" id" : 5, "name" : 'fan', "parent" : 3}, {" id ": 6," name ": 'desk lamp, "parent" : 3}, {" id ": 7," name ":' commercial electrical appliances," parent ": 1}, {" id" : 8, "name" : 'large electric heat pan, "parent" : 7}, ] permission_tree = generate_tree(permission_source, 0) print(json.dumps(permission_tree, ensure_ascii=False))Copy the code

The terminal output is as follows:

Use cache optimization algorithms

Recursive algorithms have a lot of repeated calculations, which not only occupy extra resources, but also reduce the efficiency of function execution, so recursion needs to be optimized. Cache optimization method is used to improve the efficiency of function execution.

The basic idea is to add the number of this item to a list and cache it every time the node relationship is found. This entry can be skipped when the function is iterated over and over again. The code changes are as simple as adding a cache list and control flow statement:

def generate_tree(source, parent, cache=[]):
    tree = []
    for item in source:
        if item["id"] in cache:
            continue
        if item["parent"] == parent:
            cache.append(item["id"])
            item["child"] = generate_tree(source, item["id"], cache)
            tree.append(item)
    return tree
Copy the code

At this point, the infinite class classification tree structure generation algorithm is completed. Did you learn?

This is the wechat official account Python programming reference. If you find this article helpful, please follow me. Go to the author’s column www.weishidong.com for more useful information.