Существует множество динамических структур данных, в который мы можем хранить информацию. Среди них динамические массивы, списки, бинарное дерево поиска, сети…
Данный цикл статей будет посвящен именно бинарному дереву поиска.
Бинарное (двоичное) дерево поиска — конечное множество элементов, которое либо пусто, либо содержит один элемент (корень), а остальные элементы множества делятся на два непересекающихся подмножества (каждое также является своеобразным бинарным деревом поиска). Эти подмножества называют правым и левым поддеревьями исходного дерева.
Здесь 8 — корень, от которого пошли поддеревья.
Введу небольшую теорию:
Корнем дерева называют самый верхний узел дерева.
Листовые узлы (или просто листья) — узлы самого нижнего дерева, они не имеют потомков.
Внутренний узел — любой узел, имеющий потомков, таким образом не являющийся листовым узлом.
Узел, имеющий потомков, называют узлом-родителем относительно своего потомка или потомков.
В бинарном дереве поиска каждый узел имеет не более двух узлов-потомков. По этой причине оно и называется бинарным.
Часть деревообразной структуры данных, которая может быть представлена в виде отдельного дерева называется поддеревом.
Любой узел исходного дерева вместе со всему его узлами-потомками является прддеревом.
Уровень корня дерева считают равным 0, уровень ближайших предков корня — 1, и так далее.
Глубина бинарного дерева — максимальный уровень листа дерева.
Бинарное (двоичное) дерево дерево поиска — это двоичное дерево, для которого выполняются следующие дополнительные условия:
1) У всех узлов левого поддерева произвольного узла значения ключей данных меньше, чем значения ключа самого узла
2) У всех узлов правого поддерева значения ключей данных не меньше, чем значение ключа данных узла.
3) Оба поддерева — левое и правое, являются двоичными деревьями поиска
Впрочем, теории достаточно, переходим непосредственно к коду. Для более подробной теоретической информации можно почитать статью с википедии.
Во всех своих примерах кода я буду использовать такую структуру:
struct Node { int inf1; char* name; Node* left; Node* right; };
Comments ( 0 )