Расчет глубины и потомков дерева

Question

Можете ли вы, ребята, помочь мне с алгоритмом, чтобы сделать эти вещи? Я выполнил предварительный заказ, заказ и почтовый заказ, и мне дали подсказку пройти по дереву с помощью одного из этих заказов. Я использую dotty для обозначения (или «посещения») узлов.

Глубина - это количество ребер от корня до нижнего листа, поэтому каждый раз, когда я двигаюсь, я добавляю +1 к глубине? Что-то подобное?

Нет понятия об алгоритме для потомков. Они спрашивают о количестве узлов под конкретным узлом.

Кстати, это нормальные деревья.

Answer 1

Это вопрос к домашней работе? Мой ответ предполагает, что это для домашней работы.

Деревья представляют собой рекурсивную структуру данных, поэтому алгоритмы, работающие с ними, часто будут рекурсивными. Рекурсивным алгоритмам нужен базовый случай и индуктивный случай. Для деревьев базовый случай будет тем, что вы делаете, когда вы посещаете листовой узел (то есть узел без дочерних узлов). Индуктивный случай будет тем, что вы делаете, когда вы посещаете внутренний узел (то есть узел с хотя бы одним дочерним узлом).

Для расчета глубины (или «высоты» дерева):

• Базовый случай: какова глубина узла без дочерних элементов?
• Индуктивный случай: учитывая, что у вас есть глубина всех ваших детей (которые могут быть разными), какова глубина текущего узла, который вы посещаете?

Для расчета количества потомков:

• Базовый случай: сколько потомков у узла без детей?
• Индуктивный случай: учитывая, что вы знаете количество потомков всех ваших детей, каково количество потомков текущего узла, который вы посещаете?

Я призываю вас задать уточняющие вопросы.

Answer 2

depth(tree) = 1+ max(depth(tree.left), depth(tree.right));

descendants(tree) = descendants(tree.left) + descendants(tree.right);

В любом случае возврат 0 для нулевого указателя приведет к завершению рекурсии.