Бинарное дерево — это конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев — левого и правого.

Из определения следует, что в бинарном дереве каждый узел может иметь максимум две связи, причем связь влево (если она имеется) ведет к младшему сыну, а связь вправо (если она имеется) ведет к ближайшему по старшинству брату.

На рисунке ниже приведены две диаграммы деревьев (левая и правая связь), которые изоморфны как упорядоченные, ориентированные и свободные деревья, но не изоморфны как бинарные деревья.

Для человека, немного искушенного в программировании, отличие левой связи от правой в бинарном дереве, может быть осмыслено, например, так: пусть задана структура определяющая запись и поля в базе данных (язык С++):

Допустим, что для формирования базы данных, была написана программа, которая использовала данную структуру данных. Тогда имитацию расположения данных в оперативной памяти и их нахождения, можно схематично пояснить так:

Здесь, в переменной (типа указатель) begin находится адрес F100 первого байта, из 92 выделенных, под первую запись (переменная Ivanov) нашей базы данных (здесь F100 – это имитация шестнадцатеричного адреса, например, такого 0х8800A10F, причем считаем, что следующий байт имеет адрес F101, и т.д., т.е. расчеты ведем, в привычной десятичной системе исчисления). Обращение Ivanov.left (левая связь) приведет к данным на Петрова, т.к. они располагаются по адресу F200, а обращение Ivanov.right (правая связь) приведет к данным на Сидорова, т.к. они располагаются по адресу F300. Очевидно, что представление такой схемы расположения данных в виде графа более удобно и помогает программисту создавать более изощренные структуры данных, необходимые для написания эффективно работающих программ. Правда, надо признать, что из этого примера неясно, зачем вообще надо было использовать две связи, а не обойтись одной. Но об этом чуть позже, в разделе деревья сортировки.

Мы помним, что всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Всякий упорядоченный лес (дерево) можно представить бинарным деревом, действуя по следующему правилу:

1. корень самого левого упорядоченного дерева является корнем бинарного дерева, остальные корни — его братья;

2. связи от узлов проводят так: правую связь к ближайшему старшему брату, а левую — к младшему сыну.

Утверждение. Всякому упорядоченному лесу (дереву) взаимно однозначно соответствует некоторое бинарное дерево.

Пример. На рисунке ниже приведены диаграммы упорядоченного и соответствующего ему бинарного деревьев:

Из предыдущего утверждения следует, что для представления деревьев в ЭВМ, достаточно рассмотреть представление в ЭВМ бинарных деревьев, т.к. в этом случаи ясно, что при описании структуры переменных достаточно указать два поля (left, right) и совсем не ясно, сколько полей надо отводить, для описания структуры данных в виде упорядоченного дерева.

Списочные структуры: каждый узел представляется структурой типа N, содержащей два поля (L и R) с указателями на левый и правый узлы и еще одно поле i для хранения указателя на информацию об узле. Дерево представляется указателем на корень. Тип N обычно определяется следующим образом:

На рисунке ниже представлено двоичное дерево и его представление в виде списочной структуры:

Приведенная здесь таблица наводит на мысль, что бинарное дерево можно задать при помощи двух массивов L[] и R[], при этом вершины должны соответствовать индексам массива, а L[i] и R[i] указывать на левую и правую связь узла i.