Найти максимальную степень узлов в дереве

Question

Прежде всего это вопрос домашней работы, но я не прошу решения. У меня есть некоторые идеи о том, с чего начать, но я также хотел бы получить некоторые предложения.

Это вопрос: Задать алгоритм max-degree (r), который получает в качестве входного сигнала корень r дерева, и выводит максимальную степень узлов в дереве .

Я пытался использовать метод children() для дерева ADT, но этот метод возвращает итерируемую коллекцию. Я даже не знаю, что такое итеративная коллекция или выглядит так, если бы кто-нибудь мог привести пример использования children() для древовидного объекта, что было бы очень полезно. Кроме того, если вы считаете, что я неправильно использую эту проблему, пытаясь использовать метод children(), скажите об этом.

Answer 1

Вы должны проверить всех детей и взять максимум degree. Вы можете перемещаться по дереву, как в DFS (здесь BFS требуется больше памяти). В pesudo-коде может выглядеть так:

def max-degree(vertex root) 
    solution = local_degree 
    foreach(vertex x : root.children()) 
     solution = max(solution, max-degree(x)) 
    return solution 

Особый случай является корнем дерева, если вы не хотите, чтобы принять во внимание его степень. Но это легко решить.