До сих пор мы рассматривали структуры данных, данные в которых располагаются линейно. В связном списке — от первого узла к единственному последнему. В динамическом массиве — в виде непрерывного блока.
В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.
Также смотрите другие материалы этой серии: стеки и очереди, динамический массив, связный список, оценка сложности алгоритма, сортировка и множества.
Для начала мы рассмотрим обычное дерево.
Деревья
Дерево — это структура, в которой у каждого узла может быть ноль или более подузлов — «детей». Например, дерево может выглядеть так:

Структура организации
Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный представления и хранения такой информации.
Типы и структуры данных
Под типом данных (data type) понимается множество величин, объединенных определенными признаками и совокупностью допустимых преобразований.
Так, если в качестве объединяющего признака используетс� вид данных, то данные можно разделить на следующие типы:
• символьные;
• текстовые;
• звуковые;
• графические.
Например, в MS Excel выделяются три основных типа данных: число, текст и формула.
Если в качестве объединяющего признака использовать представления данных в вычислительных системах (алгоритмических языках программирования), то данные можно разделить на следующие типы:
• целочисленный – используется для представления целых чисел;
• вещественный – используется для представления чисел с плавающей запятой (точкой);
• строковый – используется для представления строки символов;
• логический – используется для представления логических значений «ложь» или «истина»;
• указательный – используется для ссылки на другой объект и т. д.
