Блог

Главная - Вопросы по программированию - Как мне найти максимальную глубину дерева?

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

#python #tree

#python #дерево

Вопрос:

У меня есть древовидная структура данных, определенная как показано ниже:

 class Tree(object):
    def __init__(self, name='ROOT', children=None):
        self.name = name
        self.children = []
        if children is not None:
            for child in children:
                self.add_child(child)
    def __repr__(self):
        return self.name
    def add_child(self, node):
        assert isinstance(node, Tree)
        self.children.append(node)

Мне нужно написать функцию, чтобы найти глубину дерева. Вот функция, которую я написал (принимает дерево в качестве входных данных и возвращает целочисленное значение в качестве выходных данных), но она не дает правильного ответа:

 def depth(tree): 
    count = 1
    if len(tree.children) > 0:
        for child in tree.children:
            count = count   1
            depth(child)
    return count

Как мне это исправить?

Комментарии:

1. Что происходит с возвращаемым результатом при вызове depth(child) ?

2. Какое значение count имеет значение после 1?

3. Функция глубины неверна как рекурсивная функция. Вы должны установить count в качестве аргумента, например def depth(tree, count=1)

Ответ №1:

Хотя ваш depth(child) выполняет рекурсивный вызов, он ничего не делает с возвращаемым значением (глубина). Кажется, вы просто подсчитываете узлы на заданном уровне и называете это глубиной (на самом деле это ширина).

Что вам нужно, это что-то вроде (псевдокод):

 def maxDepth(node):
    # No children means depth zero below.

    if len(node.children) == 0:
        return 0

    # Otherwise get deepest child recursively.

    deepestChild = 0
    for each child in node.children:
        childDepth = maxDepth(child)
        if childDepth > deepestChild:
            deepestChild = childDepth

   # Depth of this node is one plus the deepest child.

   return 1   deepestChild

Ответ №2:

Как насчет того, чтобы просто рекурсивно увеличить максимальную глубину каждого узла?

 def max_depth(self, depth=0):
    if not self.children:
        return depth
    return max(child.max_depth(depth   1) for child in self.children)