| ВНИМАНИЕ | Для заказа программы на двоичное дерево поиска пишите на мой электронный адрес proglabs@mail.ru |
Иногда мне приходится находить количество листьев в поисковом двоичном дереве. Решил ( в первую очередь для себя ) написать эту заметку-шпаргалку, чтобы при необходимости быстро вспомнить алгоритм.
Хочу рассмотреть следующее анонимное двоичное дерево поиска:
Рисунок — стандартное анонимное бинарное дерево поиска
➡ Очевидно, чтобы найти количество листьев в бинарном дереве, необходимо знать определения термина «лист», чтобы понимать, а что, собственно, ищем-то.
Лист — узел поискового двоичного дерева, который не имеет потомков.
Тогда я отмечу все листовые узлы на рассматриваемом анонимном дереве красным цветом:
Рисунок — двоичное дерево поиска, у которого листовые вершины закрашены красным цветом
Моя задача — понять, каким образом найти все эти «красные» вершины, являющиеся листьями. То есть мне нужна функция, которая в качестве результата вернет количество листьев двоичного дерева.
Я хочу посмотреть на это анонимное поисковое бинарное дерево со всеми связями, на котором выделены красным цветом все листовые узлы с их связями:
Рисунок — бинарное дерево поиска со всеми связями его вершин
Внимательно изучив топологию этого дерева стало понятно, что листовые узлы прекращают порождение новых узлов, так как у них нет потомков ( кстати, в соответствии с их определением ). Следовательно, если встретился лист, то сразу можно делать возврат. Нет никакого смысла спускаться ниже, доходя до NULL-указателей.
Поскольку искомая программная функция должна в качестве результата возвращать количество листьев в бинарном дереве поиска, то я буду возвращать «$+1$», когда встретится лист. Понятно, что мне потребуется запустить обход вершин всего поискового дерева.
В итоге я написал следующую мощную функцию, которая считает количество листов:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//------------------------------------------------------------------------------ // нахождение количества листьев в двоичном дереве поиска //------------------------------------------------------------------------------ int Get_leafs_count( const Node* const node ) { Node_status status = Get_status_node( node ); if ( status == NONE ) { return 0; } if ( status == LEAF ) { return 1; } return Get_leafs_count( node -> left ) + Get_leafs_count( node -> right ); } //------------------------------------------------------------------------------ |
Также напомню, что собой представляет пользовательский тип данных Node_status:
|
1 2 3 4 5 6 7 8 9 10 11 |
//------------------------------------------------------------------------------ // статус узла бинарного дерева поиска //------------------------------------------------------------------------------ typedef enum Node_status { NONE, // нет узла ( NULL-указатель ) LEAF, // пустой узел ( лист - не имеет сыновей ) HALF, // половинчатый ( имеет одного сына: левого или правого ) FULL // полный ( имеет обоих сыновей ) } Node_status; //------------------------------------------------------------------------------ |
Функция Get_leafs_count является максимально универсальной. Даже, если на вход этой функции передать пустое дерево, то она корректно обработает такую ситуацию и в качестве ответа вернет $0$. При этом данная функция является достаточно сложной для понимания, так как использует каскадную рекурсию.
➡ Думаю, что теперь я легко смогу брать алгоритм и программную функцию для своих проектов, связанных с обработкой бинарного дерева поиска.
В комментариях пишите, что непонятно в рамках этой функции. Если непонятно, что это за функция Get_status_node, которая вызывается внутри функции Get_leafs_count, то попробуйте реализовать ее самостоятельно. Цель этой функции — определение статуса узла поискового дерева. Кстати, в одной из своих заметок, я детально рассказываю об этой функции и привожу ее программную реализацию.
| ВНИМАНИЕ | Для заказа программы на двоичное дерево поиска пишите на мой электронный адрес proglabs@mail.ru |
Добавить комментарий