Мне нужно написать программу, которая подсчитывает количество узлов с определенного уровня, заданное в двоичном файле .Двоичное дерево количество узлов с заданным уровнем
< Я имею в виду numberofnodes (уровень Int) {}>
Я пытался писать его без какого-либо успеха, потому что я не знаю, как добраться до определенного уровня, то идти подсчитать число узлов.
Ну, есть много способов, которыми вы можете это сделать. Лучше всего иметь одномерный массив, который отслеживает количество узлов, которые вы добавляете/удаляете на каждом уровне. Учитывая ваши требования, это был бы самый простой способ.
Однако, если он снабжен только двоичным деревом, вам нужно пройти и перейти на многие уровни и подсчитать узлы, я не вижу другой альтернативы.
Чтобы перейти на определенный уровень, вам, как правило, потребуется переменная, называемая «current_depth», которая будет отслеживать уровень, в котором вы находитесь. Как только вы достигнете своего уровня интереса и что узлы посещаются один раз (обычно a Для того, чтобы обход был достаточным), вы можете увеличить свой счет. Надеюсь, это помогло.
Сделайте это с рекурсивной функцией, которая только опускается до определенного уровня.
Я думаю, что OP просит подсчитать ** из ** определенного уровня, а не ** до ** определенного уровня. –
Я думаю, что ОП просит подсчитать ** на ** определенный уровень, но кто знает. – sth
Я предполагаю, что ваше двоичное дерево не обязательно завершено (т. Е. Не каждый узел имеет двух или нулевых детей, или это становится тривиальным). Я также предполагаю, что вы должны считать только узлы на определенном уровне, а не на этом уровне или глубже.
Существует много способов сделать то, что вы просили, но вы можете думать об этом как о проблеме поиска графа - вам предоставляется исходный узел (корень дерева), способ пересечения ребер (дочерний ссылки), а критерии - на некотором расстоянии от корня.
На данный момент вы, вероятно, изучили алгоритмы поиска графа - какой алгоритм звучит как естественная подгонка вашей задачи?
В общих чертах:
Рекурсия.
На каждой итерации рекурсии вам необходимо как-то измерить, на каком уровне вы находитесь, и, следовательно, знать, как далеко вниз по дереву вам нужно идти дальше, где вы сейчас находитесь.
рекурсии части:
Я думаю, что проще всего просто следовать рекурсивному характеру дерева с аккумулятором для отслеживания текущего уровня (или, возможно, количества оставшихся уровней).
Нерекурсивная ветвь этой функции - это когда вы попадаете на соответствующий уровень. В этот момент вы просто возвращаете 1 (потому что вы нашли один узел на этом уровне).
Рекурсивная ветвь просто суммирует количество узлов на этом уровне, возвращаемых левыми и правыми рекурсивными вызовами.
Это псевдо-код, это предполагает, что корень имеет уровень 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)
Является ли это домашнее задание? Что вы пробовали? – Johnsyweb
@Johnsyweb - Звучит подозрительно, как домашнее задание для меня –
Если это домашнее задание, пометьте его как таковой. Что вы делали? – Rubys