Глубина дерева json

У меня есть дерево вида:

{  
    "id":442500000904671234,
    "reply":0,
    "children":[  
        {  
            "id":442500532536893440,
            "reply":1,
            "children":[  
                {  
                    "id":442500826561785856,
                    "reply":1,
                    "children":[  
                        {  
                            "id":442501277688545280,
                            "reply":1,
                            "children":[  
                                {  
                                    "id":442501561940709376,
                                    "reply":1,
                                    "children":[  
                                        {  
                                            "id":442501884709199872,
                                            "reply":1,
                                            "children":[  

                                            ]
                                        }
                                    ]
                                }
                            ]
                        }
                    ]
                }
            ]
        },
        {  
            "id":442500099315597312,
            "reply":0,
            "children":[  

            ]
        }
    ]
}

Как найти максимальную глубину дерева в python?


python json depth
person Saurabh    schedule 12.03.2015    source источник
comment
Попробуйте увеличить счетчик, когда вы углубитесь с помощью {, но уменьшите его, когда вы закроете с помощью }. Каждый раз проверяйте, не превышает ли ваш счетчик ваш текущий максимум.   -  person VoidStar    schedule 12.03.2015

Ответы (5)


arrow_upward
2
arrow_downward

Вы можете проанализировать JSON с помощью библиотеки Python json, а затем вычислить глубину с помощью рекурсивной функции.

import json

def depth(jsn):
    if jsn.has_key('children'):
        return 1 +  max([0] + map(depth, jsn['children']))
    else:
        return 1

j = json.load(file('your_file.json'))
print depth(j)
person max taldykin    schedule 12.03.2015
comment
Спасибо. Это сработало, но не могли бы вы предложить мне какой-нибудь учебник по другим таким функциям, как карта. На самом деле мне нужно провести подробный анализ дерева json. - person Saurabh; 12.03.2015
comment
этот довольно удобочитаем. - person max taldykin; 12.03.2015
comment
это хорошее решение - person Humoyun Ahmad; 23.12.2016

arrow_upward
0
arrow_downward

Вы можете использовать стек, чтобы нажать {, а затем, когда вы встретите }, прежде чем вы вытолкнете, вы проверяете, больше ли ваша текущая глубина, чем максимальная глубина, которую вы получили до сих пор, то есть если stack.count больше, чем максимальное количество уже достигнуто.

Я обновлю свой ответ после работы с примером кода

person Christo S. Christov    schedule 12.03.2015
comment
Пожалуйста, дайте мне знать то же самое. Спасибо - person Saurabh; 12.03.2015
comment
Я также хочу знать количество детей на каждом уровне. - person Saurabh; 12.03.2015

arrow_upward
0
arrow_downward

Как насчет загрузки json в dict и обхода дерева. По крайней мере, должны дать некоторые идеи, чтобы пойти дальше.

import json

def depth(root):
    if root is None:
        return 0
    if isinstance(root, list):
        return max(map(depth, root)) + 1
    if not isinstance(root, dict):
        return 1
    return max(depth(v) for k, v in root.items()) + 1

print depth(json.load(file('your_data.json')))
person ferhat    schedule 12.03.2015

arrow_upward
0
arrow_downward

Я думаю, вы можете просто пройтись по дереву, используя DFS или BFS, и считать глубину по мере продвижения:

#load in your data
json_tree = json.loads(your_data)

depth = 0

if json_tree:
    depth += 1

#add a root node + it's depth
to_visit = [(json_tree, depth)] 

max_depth = 0

while to_visit:
    #get first from the list
    current = to_visit.pop(0)

    #if depth greater than the current max update max 
    if current[1] > max_depth:
        max_depth = current[1]

    # append all children to the list with increased depth
    for child in current[0]['children']:
        to_visit.append((child, current[1] + 1))


print(max_depth)

Преимущество этого способа заключается в том, что вы фактически просматриваете свою структуру данных, а не полагаетесь на строковое представление.

person user3012759    schedule 12.03.2015

arrow_upward
0
arrow_downward

конвертировать json в дикт,

count_global = 0


def find_depth(tree_dict=None, count=0):

    if not tree_dict['children']:
        global count_global
        if count_global < count:
            count_global = count

    for child in tree_dict['children']:
        count = count + 1
        find_depth(child, count)
person pnv    schedule 12.03.2015
comment
ИМО, блокировка должна быть сделана для count_global, чего я не делал! - person pnv; 12.03.2015