Алгоритм формирования бинарного дерева «снизу вверх»

1. Инициализировать очередь.

2. Последовательно обрабатывать символы последовательности, пока не достигнут концевой маркер.

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

4. Если по окончании работы алгоритма очередь окажется пустой, то сформировано пустое БД, иначе очередь будет содержать единственный элемент — корень сформированного дерева.

При обходе БД (см. рис.25) в симметричном порядке получим последовательность: .D.C.E.B.F.A.G.I.H.J.

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

 

 

. . . . .

 

 

. . . . . .

Рис.26. Бинарное дерево

 

Рассмотрим алгоритм формирования БД, в котором для любой вершины T_i значения всех вершин в левом поддереве должны быть меньше значения в вершине T_i, а в правом — больше. Такое дерево можно построить, обработав последовательность неповторяющихся значений.