Обход слева направо(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
Тогда средняя высота вычисляется следующим образом
hcp:= СДП(Root, 1)/ Размер(Root)
4) Определение контрольной суммы для дерева