В этой статье-шпаргалке я хочу показать, как найти количество вершин в заданном двоичном дереве.
➡ Абсолютно не важно — является дерево поисковым или нет, главное требование к нему, чтобы оно было бинарным.
Хочу рассмотреть следующее анонимное двоичное дерево. Почему анонимное? Потому что все узлы этого дерева не имеют ни ключей, ни каких-либо данных. Для исследования алгоритма мне это не важно!
Рисунок — стандартное анонимное бинарное дерево ( поиска )
Посчитать «глазами» количество узлов в этом дереве, используя представленную картинку, не составляет труда. Очевидно, что данное двоичное дерево содержит $11$ узлов. Но мне нужна программная функция, которая выполняет всю эту работу за меня. Выполняет быстро, правильно и надежно.
Я люблю исследовать двоичные деревья ( в том числе и поиска ), когда отображены все связи ( ветви ) между узлами, а также показан указатель на корень дерева. Поэтому рассмотрю следующее изображение:
Рисунок — анонимное бинарное дерево с указанием всех ветвей
💡 А сейчас покажу основную идею алгоритма. Для этого я пронумерую все вершины ( в хаотичном порядке ) натуральными числами от $1$ до $n$, где $n$ — общее количество узлов двоичного дерева, а также выделю оранжевым цветом некоторые ветви. В итоге у меня получилась такая картина:
Рисунок — взаимосвязь количества ветвей и количества вершин двоичного дерева
➡ И теперь я хочу посчитать количество оранжевых ветвей и количество вершин в этом дереве. Оказывается эти количества равны друг другу и составляют число $11$.
Поэтому моя задача сводится к тому, чтобы посчитать количество оранжевых ребер. Это количество и будет ответом, так как оно будет равно количеству узлов бинарного дерева.
Другой важный момент заключается в том, что NULL-ветви при обходе дерева учитывать не нужно. То есть, если исследуется NULL-ребро необходимо искомое количество увеличивать на величину $0$.
И последний штрих: необходимо уловить связь между оранжевыми ребрами и числом рекурсивных вызовов функции, которая считает искомое количество. Общее количество рекурсивных вызовов будет равно общему числу всех связей, но, как мы раньше договорились, NULL-ветви учитываться не будут ( будет возвращаться для них число $0$ ).
В результате я закодировал на языке «чистый» Си следующую компактную рекурсивную функцию ( используется каскадная рекурсия ):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//------------------------------------------------------------------------------ // нахождение количества вершин в двоичном дереве поиска // в качестве результата возвращается искомое количество вершин // если дерево пустое, то вернется значение 0 // node - указатель на текущую вершину дерева //------------------------------------------------------------------------------ int Nodes_count ( const Node* const node ) { if ( node == NULL ) { return 0; } return Nodes_count( node -> left ) + Nodes_count( node -> right ) + 1; } //------------------------------------------------------------------------------ |
➡ Повторю: количество вызовов рекурсивной функции Nodes_count() равно общему количеству всех ребер двоичного дерева. Для данного дерева это число равно $23$. Это значение легко вычисляется по формуле $2 \cdot n + 1$, где $n$ — количество вершин дерева, а величине $+1$ соответствует указатель на вершину дерева ( или самый первый вызов функции Nodes_count() ).
Если говорить о вычислительной сложности данного алгоритма, то она составляет $O( 2 \cdot n + 1 ) = O( 2 \cdot n ) + O( 1 ) = O( n )$, где $n$ — общее количество вершин заданного бинарного дерева ( поиска ). Другими словами: чтобы посчитать количество узлов дерева необходимо каждый из них обойти по одному разу. Этого достаточно!
➡ Пишите в комментариях, что непонятно в рамках рассмотренного алгоритма поиска всех элементов заданного двоичного дерева. Также напишите, при каких обстоятельствах вам потребовалось находить это количество.
| ВНИМАНИЕ | Для заказа программы на двоичное дерево ( поиска ) пишите на мой электронный адрес proglabs@mail.ru |
Добавить комментарий