ВУЗ:
Составители:
34
свою очередь является деревом. Деревья T
1
, T
2
, …, T
m
называют подде-
ревьями данного корня.
Каждый узел дерева является корнем некоторого поддерева, которое
содержится в этом дереве. Число поддеревьев данного узла называется
степенью этого узла. Узел с нулевой степенью называется концевым уз-
лом (листом). Неконцевые узлы часто называют узлами разветвления.
Каждый узел дерева T находится на некотором уровне, при этом корень
имеет уровень 1, корни его поддеревьев имеют уровень 2 и т.д.
Например, на рис. 8 узел A – корень дерева { A, B, C, D, E, F, G};
подмножества {B} и {C, D, E, F, G} – поддеревья дерева с корнем А;
узел С – корень поддерева {C, D, E, F, G}; узел C имеет уровень 2 отно-
сительно всего дерева; дерево {C, D, E, F, G} имеет три поддерева {D},
{E} и {F, G}; степень узла С равна 3; B, D, E и G – концевые узлы; F –
единственный узел степени 1; G – единственный концевой узел уровня 4.
Уровень 4
Уровень 3
Уровень 2
Уровень 1
Рис. 8. Деревья
Если в пункте b) в определении дерева имеет значение относитель-
ный порядок поддеревьев T
1
, T
2
, …, T
m
, то будем говорить, что дерево
является упорядоченным; иначе − ориентированным деревом. Заметим,
что в ориентированном дереве имеет значение только относительная ори-
ентация узлов, а не их порядок. Все рассматриваемые деревья будем
считать упорядоченными, если не оговорено противное.
Так, деревья на рис. 8 являются различными, если их считать упоря-
доченными деревьями, и одинаковыми, если эти деревья считать ориен-
тированными.
Лесом называется множество, состоящее из некоторого числа непе-
ресекающихся деревьев.
Деревья далее будем изображать с корнем вверху и пользоваться
терминологией, употребляемой при описании генеалогических деревьев.
Поэтому каждый корень дерева является отцом корней своих поддеревь-
ев, а последние являются братьями между собой и сыновьями своего
B
C
D
E
F
G
A
C
B
D
F
E
G
A
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
