Методы программирования. Громов Ю.Ю - 35 стр.

UptoLike

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

Рубрика:

отца. Заметим, что корень всего дерева отца не имеет. Кроме того, будем

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

может простираться на несколько уровней дерева.

Например, в дереве на рис. 9 узел C имеет трёх сыновей D, E и F;

узел E – отец узла G; узлы B и C – братья; узлы D, E, F и G – потомки

узла C; узлы A, C и E – предки узла G.

Рис. 9. Дерево с корнем вверху

Наиболее важным типом деревьев являются бинарные деревья.

Бинарное дерево это конечное множество узлов, которое или пусто,

или состоит из корня и самое большее двух непересекающихся би-

нарных деревьев, называемых левым и правым поддеревьями данного

дерева.

Так, если два дерева на рис. 10 считать бинарными деревьями, то

они различны.

Рис. 10. Различные бинарные деревья

Заметим, что деревья можно представлять и другими способами:

вложенными множествами (для ориентированных деревьев), вложенны-

ми скобками, уступчатым списком и десятичной системой Дьюи.

Например, дерево, заданное на рис. 9 графом, изображено на рис. 11

с помощью вложенных множеств.

J E