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

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

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

Рекурсивный алгоритм формирования бинарного дерева «в глубину»

1. Прочитать очередной символ последовательности.

2. Если прочитанный символ точка, то БД пустое, иначе создать корень, записать в него символ, построить левое поддерево, построить правое

поддерево.

Итеративный алгоритм формирования бинарного дерева «в глубину»

1. Инициализировать стек.

2. Прочитать очередной символ последовательности.

3. Если прочитанный символ точка, то БД пустое, иначе создать корень, записать в него символ, корень поместить в стек.

4. Пока стек не пуст, выполнять п.5.

5. Прочитать символ, извлечь вершину из стека. Если для вершины левое поддерево не построено, то построить его в соответствии с п.6, если не построено правое поддерево, то построить его в соответствии с п.7.

6. Если символ точка, то левое поддерево пустое, вернуть вершину в стек, иначе создать корень левого поддерева, записать в него символ, вернуть в стек вершину, созданный корень поместить в стек.

7. Если символ точка, то правое поддерево пустое, иначе создать корень правого поддерева, записать в него символ, созданный корень поместить в стек.

Если при прохождении БД (см. рис.21) в прямом порядке сначала дерево, а потом все поддеревья заключать в скобки, то получим скобочное представление БД:

(A(B(C(D()())(E()()))(F()()))(G()(H(I()())(J()())))

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

При обходе БД (см. рис.25) «в ширину» получим последовательность: ABGCF.HDE..IJ. . . . . . . .

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