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

Сентябрь 7, 2022

Главная
Алгебра
Вычисление основных характеристик дерева

Содержание

2. Вычисление основных характеристик дерева Определение контрольной суммы для дерева Алгоритм на псевдокоде int Сумма (Vertex *p)
3. Вычисление основных характеристик дерева Определение высоты дерева Алгоритм на псевдокоде int Высота (Vertex *p) IF (p
4. Вычисление основных характеристик дерева Определение средней высоты дерева hcp := СуммаДлинПутей (Root, 1) / Размер (Root)
5. Дерево поиска Логическая функция Дерево поиска определяет, является ли двоичное дерево деревом поиска. Функция возвращает значение:
7. Скачать презентацию

Слайд 2

Вычисление основных характеристик дерева
Определение контрольной суммы для дерева
Алгоритм на псевдокоде
int Сумма

(Vertex *p)
IF (p = NIL) s := 0
ELSE s := p→Data + Сумма (p→Left) +
+ Сумма (p→Right)
FI
Вызов процедуры: Сумма(Root)

Слайд 3

Вычисление основных характеристик дерева
Определение высоты дерева
Алгоритм на псевдокоде
int Высота (Vertex *p)
IF

(p = NIL) h := 0
ELSE h := 1 + max (Высота (p→Left) +
+ Высота (p→Right))
FI
Вызов процедуры: Высота(Root)

Слайд 4

Вычисление основных характеристик дерева
Определение средней высоты дерева
hcp := СуммаДлинПутей (Root, 1)

/ Размер (Root)
Алгоритм на псевдокоде
СуммаДлинПутей (Vertex*p; int L- уровень вершины)
IF (p = NIL) s := 0
ELSE s := L +
+ СуммаДлинПутей (p → Left, L+1) +
+ СуммаДлинПутей (p → Right, L+1)
FI

Слайд 5

Дерево поиска
Логическая функция Дерево поиска определяет, является ли двоичное дерево деревом

поиска.
Функция возвращает значение:
ИСТИНА, если дерево является деревом поиска, ЛОЖЬ, если не является.
Функция состоит из одного условного оператора!