Бинарное дерево - это иерархическая динамическая структура данных, состоящая из узлов и соединяющих их дуг. В каждый узел, кроме одного, ведет ровно одна дуга. Этот единственный узел называется корнем дерева.
С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями. На рисунке изображено дерево, в узлах которого располагаются символы:
Вершина Y, находящаяся непосредственно ниже вершины X, называется непосредственным потомком X, а вершина X называется предком Y. Если вершина не имеет потомков, то она называется листом, если имеет, то называется внутренней вершиной. Например, вершины D, E являются непосредственными потомками вершины B; вершины H, I, J являются листьями. Очевидно, что для описания дерева требуются ссылки. Опишем бинарное дерево как структуру типа Record, содержащую как минимум два поля – указатели на левое и правое поддеревья, и поле данных, например типа Integer:
Type PTree = ^TTree; TTree = Record Data : Integer; Left, Right : PTree; end;Корень дерева описывается ссылочной переменной:Var Tree : PTree;