Введение в информационные системы. Брюхомицкий Ю.А. - 69 стр.

UptoLike

Составители:

Рубрика:

При описании деревьев иногда применяют терминологию, используе-

мую при описании генеалогических деревьев (предки-потомки, отцы-сыновья и

т.п.).

Древовидные структуры данных более удобны для реализации в памяти

ЭВМ, чем сетевые, и требуют менее сложного программного обеспечения. По-

этому в ряде случаев сетевые структуры заменяются совокупностью деревьев.

При этом сложные

сети вначале приводятся к простым, а затем простые сети

заменяются деревьями.

Сложные сети приводятся к простому виду путем введения избыточно-

сти. При этом все элементы сложной сети повторяются дважды, как это показа-

но на рис. 5.16.

Затем простые сети заменяются деревьями также путем введения избы-

точности. При этом ряд элементов сети также

повторяется (рис. 5.17).

Рис. 5.16. Приведение сложной сети к двум простым сетям

Рис. 5.17. Замена простых сетей деревьями

Типы деревьев. В зависимости от условий, которым удовлетворяет то

или иное дерево, выделяют различные типы деревьев.

Среди различных деревьев выделяются два важных частных случая: по-

следовательное дерево, представляющее

собой последовательную цепь, и

звездное дерево, в котором одна из вершин (центр) смежна со всеми остальны-

ми вершинами (рис. 5. 18). Последовательное дерево имеет только две концевые

32 3 2 3

1 1 1

= +

2 2 3

2 2 1

= =