Реферат: Отображение АСД на СДХ

Если T ... T - деревья, то

Дерево называется k-ичным, если все вершины имеют степень исхода k.

Дерево называется линейным, степень исхода равна 1.

ЗАДАЧА. Подсчитать количество деревьев, имеющих n вершин.

РЕШЕНИЕ. B - число деревьев из i вершин. Следуя рекурсивному определению дерева:

Þ

Дерево совершенное, если любой путь от корня к листу отличается не более чем на 1 от самого длинного пути.

Совершенное дерево из n вершин имеет минимальную высоту.

Свойства совершенных деревьев:

- составляют минимальную часть всех деревьев,

- все пути от корня к листу равноправны.