Хочу рассмотреть следующее двоичное дерево ( в данном случае — поисковое ):
Рисунок — обыкновенное двоичное поисковое дерево
➡ Для начала надо понять, как нумеруются уровни дерева, на каком уровне лежит корневая вершина и т.п.
Следующая картинка дает ответы на подобные вопросы:
Рисунок — уровни двоичного дерева
Из рисунка видно, что корневая вершина лежит на первом уровне. Иногда в теории алгоритмов нумерацию уровней бинарного дерева начинают с $0$. По-большему счету это непринципиально и мало влияет на логику алгоритма определения количества узлов на заданном уровне.
Визуально посчитаем количество вершин, а также их ключевые значения на каждом уровне рассматриваемого бинарного дерева и сведем информацию в сводную таблицу:
| # уровня | Количество вершин | Значения вершин |
| $1$ | $1$ | $52$ |
| $2$ | $2$ | $45,\ 125$ |
| $3$ | $3$ | $24,\ 88,\ 154$ |
| $4$ | $4$ | $61,\ 100,\ 132,\ 167$ |
| $5$ | $3$ | $82,\ 102,\ 155$ |
| $6$ | $2$ | $74,\ 118$ |
| $7$ | $0$ | $—$ |
💡 Но хочу напомнить, что моя задача — написать программную функцию, которая вычисляет количество вершин на заданном ( $N$-ом ) уровне двоичного дерева.
То есть меня мало интересуют значения вершин ( ключевые данные ), а лишь их количество. Из этого следует, что мне не важно, является бинарное дерево поисковым или нет. Поэтому сейчас покажу анонимное двоичное дерево аналогичной топологии:
Рисунок — уровни анонимного двоичного дерева ( поиска )
Например, пользователь «говорит», что хочет узнать количество вершин на $5$-ом уровне. Моя программная функция должна в качестве результата выдать ответ $3$, так как на уровне #$5$ находится три вершины:
Рисунок — на уровне #$5$ находится $3$ вершины
➡ Если пользователь сделает запрос по номеру уровня, которого не существует в двоичном дереве, то программа должна выдать ответ $0$. Например, уровня #17 в анализируемом анонимном двоичном дереве нет физически, поэтому и узлов на этом уровне также нет физически.
Кстати, в одной из своих статей-шпаргалок я показывал, как реализовать поуровневый вывод вершин бинарного дерева ( поиска ). Мне пришлось задействовать классическую структуру данных «Очередь» ( Queue, FIFO — First-In, First-Out ). Весь процесс был построен итеративно, то есть без рекурсии. В текущем алгоритме ( нахождения количества узлов на заданном уровне ) мне не придется прибегать к вспомогательным структурам данных и, думаю, все реализую рекурсивно в одной компактной функции.
💡 Основная идея алгоритма определения количества узлов двоичного дерева ( поиска ) на заданном ( $N$-ом ) уровне: так как до каждой вершины дерева существует строго один путь от корневой вершины ( корень лежит на уровне #$1$ ), то я буду рекурсивно перебирать все пути до тех пор, пока не будет достигнут заданный уровень или NULL.
Под перебором я понимаю стандартный обход двоичного дерева. Всего их существует $6$ штук. Я выберу LKP-обход ( симметричный левый, левый-корень-правый ).
Если в процессе обхода дерева я вышел на заданный уровень, то дальше спускаться по дереву смысла нет, поэтому это будет окончанием рекурсивного спуска для текущего пути и в качестве ответа верну из функции $1$.
В результате закодировал на языке «чистый» Си следующую функцию, а также поставил детальные комментарии к каждой строке кода:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
//------------------------------------------------------------------------------ // определение количества узлов на заданном уровне ( корень лежит на уровне #1 ) // node - указатель на анализируемый узел двоичного дерева // number_current_level - номер текущего уровня дерева, на котором находится node // number_target_level - номер заданного уровня бинарного дерева // в качестве ответа возвращается количество узлов, принадлежащих заданному уровню //------------------------------------------------------------------------------ int Nodes_count_on_target_level( const Node* const node, const int number_current_level, const int number_target_level ) { // если путь закончился быстрее, чем был достигнут заданный уровень if ( node == NULL ) { return 0; } // когда номер текущего уровня совпал с номером заданного уровня, то // мы достигли узла, принадлежащего заданному уровню и этот узел надо учесть if ( number_current_level == number_target_level ) { return 1; } // если при обходе номер текущего уровня МЕНЬШЕ, чем номер заданного уровня, то // продолжаем LKP-обход дерева ( постепенно погружаясь "внутрь" дерева ) return Nodes_count_on_target_level( node -> left, number_current_level + 1, number_target_level ) + Nodes_count_on_target_level( node -> right, number_current_level + 1, number_target_level ); } //------------------------------------------------------------------------------ |
Вызов этой функции сделать можно так:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int nodes_count; // хранит результат ( количество вершин на заданном уровне дерева ) int number_target_level; // номер уровня // вводим с клавиатуры входные данные: номер уровня printf( "\nВведите #уровня двоичного дерева для поиска количества узлов на нем: " ); scanf( "%d%*c", &number_target_level ); // вызываем функцию нахождения количества узлов, расположенных на заданном уровне // вторым параметром стоит 1, так как спуск по дереву начинается с корня, а корень лежит на уровне #1 // выводим результат на экран пользователю nodes_count = Nodes_count_on_target_level( root, 1, number_target_level ); printf( "Количество узлов на уровне #%d: %d шт.", number_target_level, nodes_count ); |
➡ Функция Nodes_count_on_target_level() является универсальной и она корректно работает, даже если на вход передать указатель на пустое двоичное дерево ( поиска ) — в этом случае ответ будет равен $0$, что абсолютно правильно.
Если в качестве заданного уровня передать недостижимый уровень, то функция также вернет $0$ и ошибок никаких не будет.
Еще такой момент: на самом деле функцию нахождения числа узлов на заданном уровне легко адаптировать, например, для поиска количества не всех узлов, а лишь полных узлов, листьев и т.п.
Пишите в комментариях, что непонятно в алгоритме нахождения количества элементов двоичного дерева ( поиска ), расположенных на заданном уровне. Если на практике вам приходилось сталкиваться с этим алгоритмом, то в рамках какой задачи — расскажите об этом.
| ВНИМАНИЕ | Для заказа программы на бинарное дерево ( поиска ) пишите на мой электронный адрес proglabs@mail.ru |
Добавить комментарий