| ВНИМАНИЕ | Для заказа программы на двоичное дерево поиска пишите на мой электронный адрес proglabs@mail.ru |
За основу возьмем узлы дерева, ключами которых выступают целые числа. То есть будем исследовать бинарное дерево поиска, построенное на базе целых чисел.
На рисунке ниже приведен пример такого двоичного дерева поиска со всеми связями.
На этом рисунке есть стрелочки, указывающие на горизонтальную линию — так в теории деревьев допустимо обозначать указатель на NULL ( NIL, nullptr и т.п. ).
Так как бинарное дерево поиска состоит из набора узлов, причем структурно узлы неотличимы друг от друга, то становится очевидным, что все узлы дерева имеют абсолютно идентичную структуру, а именно:
- место для хранения данных (данные в том числе включают и ключ);
- указатель на левое поддерево;
- указатель на правое поддерево;
💡 Так как мы рассматриваем «бинарку», построенную на базе целых чисел, то ключом выступают и сами данные, то есть ключ и данные выражают одно и то же — целое число. Когда данные являются комплексными/составными, то имеет место разделение, собственно на сами данные и на ключевое значение.
Кстати, в английском языке слово «узел» пишется как «node», следовательно, опишем на языке программирования Си тип данных, который характеризует узел двоичного дерева поиска:
|
1 2 3 4 5 6 7 |
// описание структуры узла бинарного дерева поиска typedef struct Node { int key; // ключевое значение узла struct Node* left; // указатель на левое поддерево struct Node* right; // указатель на правое поддерево } Node; |
В языке программирования Си только указателям можно присваивать значения NULL, чтобы они не были висячими и не указывали на неизвестный участок динамической области памяти.
Хочется отметить еще такой момент, что в редких случаях орудуют двоичным деревом поиска, узлы которого имеют связь со своим предком/родителем ( рисунок ниже ).
|
1 2 3 4 5 6 7 8 |
// описание структуры узла бинарного дерева поиска с указателем на родителя typedef struct Node { int key; // ключевое значение узла struct Node* parent; // указатель на родительский узел struct Node* left; // указатель на левое поддерево struct Node* right; // указатель на правое поддерево } Node; |
Это связано с тем, что иногда требуется проводить какие-то нестандартные операции над «бинаркой» ( например, поиск пути или полупути ), и в этом случае требуется подниматься по дереву к корню. В таких ситуациях указатель на родителя оказывается чрезвычайно полезным.
➡ Также указатель на своего предка полезен, когда происходит балансировка дерева, но в этом случае правильнее упоминать AVL-дерево.
Пишите в комментариях, какие виды узлов двоичного дерева поиска с точки зрения своей структуры вы встречали на практике.
| ВНИМАНИЕ | Для заказа программы на двоичное дерево поиска пишите на мой электронный адрес proglabs@mail.ru |
Добавить комментарий