Построение бинарного дерева

Важным понятием древовидной структуры является понятие двоичного дерева поиска. Правило построения двоичного дерева поиска: элементы, у которых значение некоторого признака меньше, чем у корня, всегда включаются слева от некоторого поддерева, а элементы со значениями, большими, чем у корня - справа. Этот принцип используется и при формировании двоичного дерева, и при поиске в нем элементов. Таким образом, при поиске элемента с некоторым значением признака происходит спуск по дереву, начиная от корня, причем выбор ветви следующего шага - направо или налево согласно значению искомого признака - происходит в каждом очередном узле на этом пути. При поиске элемента результатом будет либо найденный узел с заданным значением признака, либо поиск закончится листом с «нулевой» ссылкой, а требуемый элемент отсутствует на проделанном по дереву пути. Если поиск был проделан для включения очередного узла в дерево, то в результате будет найден узел с пустой ссылкой (пустыми ссылками), к которому справа или слева в соответствии со значением признака и будет присоединен новый узел.

Рассмотрим пример формирования двоичного дерева. Предположим, что нужно сформировать двоичное дерево, узлы (элементы) которого имеют следующие значения признака: 20, 10, 35, 15, 17, 27, 24, 8, 30. В этом же порядке они и будут поступать для включения в двоичное дерево. Первым узлом в дереве (корнем) станет узел со значением 20. Обратить внимание: поиск места подключения очередного элемента всегда начинается с корня. К корню слева подключается элемент 10. К корню справа подключается элемент 35. Далее элемент 15 подключается справа к 10, проходя путь: корень 20 - налево - элемент 10 - направо - подключение, так как дальше пути нет. Процесс продолжается до исчерпания включаемых элементов. Результат представлен на рис.