ВУЗ:
Составители:
65
Любое дерево можно рассматривать как корневое дерево (рис. 5.12).
Вершины дерева организованы по уровням и подчинены определенной иерар-
хии.
Рис. 5.12. Пример трехуровневого корневого дерева
Любой узел дерева связан с единственным узлом более высокого уров-
ня – порождающим узлом и с m узлами ближайшего низшего уровня – порож-
денными
узлами. Единственный узел, с которого начинается дерево, называется
корнем. Конечные узлы, не имеющие порожденных, называются листьями де-
рева. Промежуточные узлы, имеющие как порождающие, так и порожденные
узлы, называются ветвями дерева.
В деревьях возможна только одна ориентация – от порождающего узла
к порожденному, поэтому дуги в них обычно заменяются ребрами. Длина
пути
от корня до некоторого узла равна уровню этого узла. Уровень узла, на котором
он расположен, определяет значение этого узла. Количество уровней дерева
определяет высоту дерева.
Вершины, смежные с корнем дерева, можно рассматривать как корни
субдеревьев, которые «вырастают» из этих вершин и являются частями исход-
ного дерева, называемыми факторами. В
общем случае любую вершину графа
можно рассматривать как корень некоторого фактора, причем концевые верши-
ны – это корни тривиальных деревьев, состоящие из единственной вершины и
не содержащие ребер. В качестве веса вершины принимается общее число вер-
шин фактора, корнем которого она является. На каждом уровне факторы распо-
лагаются в порядке возрастания
весов их корней (при равенстве весов порядок
безразличен).
На рис. 5.13 корневое дерево изображено в стандартном виде и указаны
веса всех его вершин (вес корня дерева равен числу всех его вершин, а веса
концевых вершин равны единице).
Корень
Листья
Ветви
Уровень 0
Уровень 1
Уровень 2
Уровень 3
0
Страницы
- « первая
- ‹ предыдущая
- …
- 63
- 64
- 65
- 66
- 67
- …
- следующая ›
- последняя »
