Как реализовать DFS с рекурсивной функцией на JSON dict дерева? - PullRequest
Новая
       8

Как реализовать DFS с рекурсивной функцией на JSON dict дерева?

0 голосов
/ 26 апреля 2018

Я использую рекурсивную функцию Depth-First-Search для обхода дерева, где у каждого узла есть индекс.

Во время обхода мне нужно назначить один узел (тип которого dict) переменной для дальнейшей обработки из внешней области.

Кажется, я использую бесполезное задание. Какой самый эффективный способ сделать это? 

def dfs(json_tree, index, result):
    if json_tree['index'] == index:
        result = json_tree['index']   ## not work!
        return
    if 'children' not in json_tree:
        return
    for c in json_tree['children']:
        dfs(c, index, result)

1 Ответ

0 голосов
/ 26 апреля 2018

Попробуйте return результат. Обратите внимание, что я изменил вашу подпись функции. Это также приведет к короткому замыканию поиска, как только будет найден индекс. 

def dfs(json_tree, index):
    if json_obj['index'] == index:
        return json_tree['index']
    if 'children' not in json_obj:
        return None
    for c in json_tree['children']:
        result = dfs(c, index)
        if result is not None:
            return result
    return None

Редактировать : обновляется с указанием окончательного пути возврата в случае, если индекс не найден.

...