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

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

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