ВУЗ:
Составители:
66
Рис. 5.13. Стандартное представление корневого дерева
При таком представлении корневое дерево однозначно определяется
упорядоченной последовательностью
(Т) весов его вершин, в которой на пер-
вом месте стоит вес корня дерева, а затем следуют соответствующие последова-
тельности для факторов в порядке возрастания весов их корней. В свою очередь
каждая последовательность для фактора строится по тому же принципу: на пер-
вом месте стоит вес корня фактора, а затем
следуют последовательности для
факторов данного фактора и т.д. Так, для корневого дерева, изображенного на
рис. 5.13, указанная последовательность будет иметь вид
(Т) = (17, 1, 4, 1, 1, 1, 11, 4, 1, 2, 1, 6, 1, 1, 3, 1, 1).
Количество членов последовательности
(Т) равно числу вершин де-
рева. Различным корневым деревьям соответствуют и различные последова-
тельности
(Т). Достаточным критерием идентичности корневых деревьев
является совпадение соответствующих им последовательностей.
Построение корневого дерева Т по его последовательности начинается с
корня, которому соответствует первый член этой последовательности. Затем
(Т) разбивается на последовательности факторов так, что каждая из них начина-
ется членом, не меньшим, чем предыдущая, т.е.
(Т
1
) = (1);
(Т
2
) = (4,1,1,1);
(Т
3
)= (11,4,1,2,1,6,1,1,3,1,1).
Из каждой такой последовательности удаляем первые члены и соединя-
ем соответствующие им вершины с корнем. Затем поступаем аналогично до тех
пор, пока не будут исчерпаны все члены. Так, после построения корней фактора
17
4
11
6
4
У
р
овни
3
4
1
2
0
1
1 1 1
1 2
1
11
3
11
Страницы
- « первая
- ‹ предыдущая
- …
- 64
- 65
- 66
- 67
- 68
- …
- следующая ›
- последняя »
