Информатика • 11 класс

Реализация деревьев. Бинарные деревья (Паскаль)

Дерево – это структура данных, где элементы (узлы) связаны отношениями «родитель-потомок».
Бинарное дерево – частный случай дерева, где каждый узел имеет не более двух потомков.
Обозначения: T – узел общего дерева, B – узел бинарного дерева, d – данные, c – дети, l – левый потомок, r – правый потомок, n – текущий узел, r – корень дерева, a, b – временные узлы.

Аспект	Общее дерево	Бинарное дерево
Структура узла	type P = ^T; T = record d: integer; c: array of P; End.	type P = ^B; B = record d: integer; l, r: P; End.
Количество потомков	Любое количество	Только 0, 1 или 2
Создание узлов	var r, a, b: P; Begin New (r); r^.d := 1; SetLength (r^.c, 2); New (a); a^.d := 2; New (b); b^.d := 3; r^.c [0] := a; r^.c [1] := b; End.	var r, a, b: P; Begin New (r); r^.d := 1; New (a); a^.d := 2; New (b); b^.d := 3; r^.l := a; r^.r := b; End.

Было полезно?