Traverse a data structure in python that involves nesting lists and nesting dictionaries-CodePudding

I am trying to traverse this kind of tree, the idea is to get all "titles". Notice that this structure can get bigger, it means that every title can get more subcategories in the future. any idea?

I am tryin to do this:


def continue_searching(item):
    for i in len(item):
        if categories[i]["subcategories"]:
            continue_searching(i["subcategories"])
            print(i["subcategories"])


def give_titles(categories):
    for i in len(categories):
        if categories[i]["subcategories"]:
            continue_searching(i["subcategories"])
        print(i['title'])


categories = [
    {
        "title": "Food",
        "subcategories": [
            {"title": "Bread"},
            {
                "title": "Meat",
                "subcategories": [
                    {"title": "Pork",
                     "subcategories": [
                         {"title": "White Pork"},
                         {"title": "Red Pork"}
                     ]
                     },
                    {"title": "Beef"},
                ],
            },
            {"title": "Cheese"},
        ],
    },
    {"title": "Drinks"},
]

give_titles(categories)

Expected output:

Food
-Bread
-Meat
--Pork
---White Pork
---Red Pork
--Beef
-Cheese
Drinks

Notice that i am not using recursion because it is not clear for me when stop the calls and i do not want to saturate the call stacks.

CodePudding user response：

Define this function:

def write_titles(cats, depth=0):
  for c in cats:
    print('-'*depth, c['title'])
    write_titles(c.get('subcategories', []), depth 1)

Then call it using write_titles(categories).

CodePudding user response：

Traversing and printing a data structure like this is usually done using recursion as you've attempted.

In case of your code, we want to call a function repeatedly on every further nesting of the data structure.

Example code:

def print_titles(categories, depth=0):
    for category in categories:
        print('-' * depth, category['title'])
        if 'subcategories' in category:
            print_titles(category['subcategories'], depth   1)

CodePudding user response：

You could use recursive programming

def get_all_titles(data, output=[]):
    if isinstance(data, dict):
            output.append(data.get("title"))
            data = data.get("subcategories", [])
    if isinstance(data, list):
            for item in data:
                    get_all_titles(item)
    return output

Output

print(get_all_titles(categories))
['Food', 'Bread', 'Meat', 'Pork', 'White Pork', 'Red Pork', 'Beef', 'Cheese', 'Drinks']

CodePudding user response：

The structure you've defined is essentially a list of separate trees.

I just iterated over each "tree" in the list and did a preorder traversal of the tree.

categories = [
{
    "title":         "Food",
    "subcategories": [
        {"title": "Bread"},
        {
            "title": "Meat",
            "subcategories": [
            {"title": "Pork",
                "subcategories": [
                {"title": "White Pork"},
                {"title": "Red Pork"}
                ]
            },
            {"title": "Beef"},
            ],
        },
        {"title": "Cheese"},
        ],
},
{"title": "Drinks"},
]


# What's really defined here is like a list of trees

def preorder(root, depth):
    print("-" * depth   root["title"])
    if "subcategories" in root:
        for child in root["subcategories"]:
            preorder(child, depth   1)


def printCategories(categories):
    for tree in categories:
        preorder(tree, 0)
    
printCategories(categories)

This outputs:

Food
-Bread
-Meat
--Pork
---White Pork
---Red Pork
--Beef
-Cheese
Drinks

Since you also mentioned that you do not want to use recursion, just perform the traversal using your own stack as shown here.

CodePudding user response：

def all_titles(data, output=[]):

    if x(data, dict):
            output.append(data.get("title"))
            data = data.get("subcategories", [])
    
    if x(data, list):
            for y in data:
                    all_titles(item)
    return