Двоичное дерево количество узлов с заданным уровнем

Question

Мне нужно написать программу, которая подсчитывает количество узлов с определенного уровня, заданного в двоичном дерево.

Я имею в виду

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

Answer 1

Делайте это с помощью рекурсивной функции, которая опускается только до определенного уровня.

Answer 2

Это псевдокод, предполагается, что корень имеет уровень 0

int count(x,currentLevel,desiredLevel)
    if currentLevel = desiredLevel
        return 1
    left = 0
    right = 0
    if x.left != null
        left = count(x.left, currentLevel+1, desiredLevel
    if x.right != null
        right = count(x.right, currentLevel+1, desiredLevel
    return left + right

Таким образом, чтобы получить количество узлов для уровня 3, вы звоните

count(root,0,3)

Answer 3

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

Нерекурсивная ветвь этой функции - когда вы попадаете на соответствующий уровень. В этот момент вы просто возвращаете 1 (потому что вы нашли один узел на этом уровне).

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

Answer 4

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

1. Какие у вас базовые случаи? при каких условиях вы говорите: «Хорошо, время прекратить рекурсию»?
2. Как вы можете считать что-то в рекурсии без какого-либо глобального подсчета?

Answer 5

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

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

В этот момент вы, вероятно, изучили алгоритмы поиска в графике - какой алгоритм звучит естественным образом для вашей задачи?

Answer 6

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

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

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