Алгоритм на псевдокоде. Обход слева направо(p: pVertex)

Обход слева направо(p: pVertex)

IF (p ≠ NIL)

Обход слева направо (p→Left)

Печать (p→Data)

Обход слева направо (p→Right)

FI

9.3 Вычисление основных характеристик дерева

Приведем алгоритмы для вычисления различных характеристик двоичных деревьев.

1) Определение размера дерева

Алгоритм на псевдокоде

Размер(p: pVertex)

IF (p = NIL) Размер:= 0

ELSE Размер:= 1 + Размер (p→Left) + Размер (p→Right)

FI

2) Определение высоты дерева

Алгоритм на псевдокоде

Высота(p: pVertex)

IF (p = NIL) Высота:= 0

ELSE Высота:= 1+ max(Высота (p→Left), Высота(p→Right))

FI

3) Определение средней высоты дерева

Для определения средней высоты дерева понадобится функция вычисления суммы длин путей от корня до каждой вершины на L-том уровне.

Алгоритм на псевдокоде

СДП (p: pVertex; L: уровень вершины)

IF (p = NIL) СДП:= 0

ELSE СДП:= L + СДП(p → Left, L+1) + СДП(p → Right, L+1)

FI

Тогда средняя высота вычисляется следующим образом

h_cp:= СДП(Root, 1)/ Размер(Root)

4) Определение контрольной суммы для дерева