Алгоритмы формирования бинарного дерева

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

уровень 0

уровень 1

. уровень 2

.. уровень 3

........ уровень 4

Рис.25. БД с фиктивными вершинами

При обходе БД (см. рис.25) в прямом порядке получим последовательность: ABCD..E..F..G.HI..J.. Из полученной последовательности следует, что вершины A,B,C,D и H имеют по два сына, причем левый сын записан непосредственно за отцом, вершины D,E,F,I и J — листья (за ними следуют две точки), вершина G не имеет левого сына (одна точка за этой вершиной), а правый сын — H.

Сформировать БД исходя из данной последовательности можно рекурсивным и итеративным способом, причем БД будет строиться «в глубину».