Algorithm application scenario

There are many application scenarios of the infinite classification tree structure. For example, the back-end research and development needs to read out user permissions and generate a tree structure. After the front-end research and development gets the tree structure, the columns that users have permissions to access can be displayed according to the structure.

The data store information is as follows
[{"id":1."name":"Electrical"."parent":0},
    {"id":2."name":"Fruit"."parent":0},
    {"id":3."name":"Household Appliances"."parent":1},
    {"id":4."name":"Hair dryer"."parent":3},
    {"id":5."name":"Electric fan"."parent":3},
    {"id":6."name":"Lamp"."parent":3},
    {"id":7."name":"Commercial Appliances"."parent":1},
    {"id":8."name":"Large electric cooker"."parent":7},]Copy the code
Implementation of algorithm

The parent field records the parent number of this item. For example, the parent number of the hairdryer is 3, which means that the hairdryer belongs to the household appliance, while the parent number of the household appliance is 1, which means that the household appliance belongs to the electrical appliance. The hairdryer item is not directly associated with the electrical appliance item, but it needs to be indicated by a tree structure. The relationship between electrical appliance <- household appliance <- hairdryer is found by parent, and the operation of establishing the relation is actually cyclic until all nodes are found, which is very suitable with the recursive algorithm

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

Generate_tree (); generate_tree (); generate_tree (); generate_tree (); generate_tree ()

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":"Electrical"."parent":0},
    {"id":2."name":"Fruit"."parent":0},
    {"id":3."name":"Household Appliances"."parent":1},
    {"id":4."name":"Hair dryer"."parent":3},
    {"id":5."name":"Electric fan"."parent":3},
    {"id":6."name":"Lamp"."parent":3},
    {"id":7."name":"Commercial Appliances"."parent":1},
    {"id":8."name":"Large electric cooker"."parent":7},
]
permission_tree = generate_tree(permission_source, 0)
print(json.dumps(permission_tree, ensure_ascii=False))
Copy the code

And you get something like this

[{
	"id": 1."name": "Electrical"."parent": 0."child": [{
		"id": 3."name": "Household Appliances"."parent": 1."child": [{
			"id": 4."name": "Hair dryer"."parent": 3."child": []}, {"id": 5."name": "Electric fan"."parent": 3."child": []}, {"id": 6."name": "Lamp"."parent": 3."child": []}]}, {"id": 7."name": "Commercial Appliances"."parent": 1."child": [{
			"id": 8."name": "Large electric cooker"."parent": 7."child": []}]}, {"id": 2."name": "Fruit"."parent": 0."child": []}]Copy the code
Use caching algorithms for optimization

Recursive algorithm has a lot of repeated computation, these calculations not only takes up extra resources, also can reduce function execution efficiency, so you need to optimize the recursive algorithm Basic idea is to this purpose after each find a relationship between nodes number add to the list of a cached, on behalf of this entry to find the node, when the reciprocating execution function to meet the entry can be skipped, Code changes are simple

import json
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
if __name__ == "__main__":
    permission_source = [
    {"id":1."name":"Electrical"."parent":0},
    {"id":2."name":"Fruit"."parent":0},
    {"id":3."name":"Household Appliances"."parent":1},
    {"id":4."name":"Hair dryer"."parent":3},
    {"id":5."name":"Electric fan"."parent":3},
    {"id":6."name":"Lamp"."parent":3},
    {"id":7."name":"Commercial Appliances"."parent":1},
    {"id":8."name":"Large electric cooker"."parent":7},
]
permission_tree = generate_tree(permission_source, 0)
print(json.dumps(permission_tree, ensure_ascii=False))
Copy the code