Рекурсивный алгоритм формирования бинарного дерева «в глубину»
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. . . . . . . .
Используя эту последовательность в качестве исходных данных можно сформировать БД, применив алгоритм формирования БД «в ширину».
Алгоритм формирования бинарного дерева «в ширину»
1. Инициализировать очередь.
2. Прочитать очередной символ последовательности.
3. Если прочитанный символ точка, то БД пустое, иначе создать корень, записать в него символ, корень поместить в очередь.
4. Пока очередь не пуста, выполнять п.5.
5. Взять вершину из очереди. Прочитать символ. Если символ точка, то левое поддерево пустое, иначе создать корень левого поддерева, записать в него символ и включить в очередь. Прочитать следующий символ. Если символ точка, то правое поддерево пустое, иначе создать корень правого поддерева, записать в него символ и включить в очередь.
При обходе БД (см. рис.25) в обратном порядке получим последовательность: ..D..EC..FB...I..JHGA
Если ограничить эту последовательность концевым маркером, то ее можно будет использовать в качестве исходных данных для формирования БД «снизу вверх».