Структуры данных
Категория реферата: Рефераты по математике
Теги реферата: шпоры по социологии, антикризисное управление
Добавил(а) на сайт: Кир.
Предыдущая страница реферата | 1 2 3 4 5 | Следующая страница реферата
Деревья могут быть как ориентированные так и нет.
Определение.
Высотой дерева называется самый длинный путь в дереве из корня к листу.
Примеры.
1. Группа родственников с отношением быть ребенком;
2. Дерево игры;
3. Слова в алфавите: разбиваются на классы эквивалентности по первому символу, каждый класс в свою очередь разбивается на классы эквивалентности по второму символу и т.д.
Определение.
Не связный ациклический граф называется лесом.
Рекурсивное определение дерева.
1.Множество из одной вершины - дерево;
2.Если Т1, Т2, ...ТN - деревья, то вершина
T1 T2 T3 ... TN - дерево
Основные операции над деревьями:
найти заданную вершину;
заменить одну заданную вершину на другую;
удалить вершину;
вставить новую вершину.
При построении алгоритмов, реализующих эти равно как и другие операции над деревьями надо учитывать, что в дереве возможны самые разнообразные последователльности промотра вершин. Было бы полхо если результат операции зависел бы от порядка обхода дерева. Основные направления обхода: сверху-вниз, снизу-вверх, справа-налево, слева-направо.
Определение.
Дерево называется K-ичным если все внутренние вершины в нем имеют степень исхода K.
Соответсвенно дерево называется единичным или линейным, если степень исхода его внутренних вершин равна 1; в двоичном или бинарном дереве она соответсвенно равна 2.
Перечисление бинарных деревьев.
Попробуем подсчитать число двоичных деревьев, имеющих n вершин. Обознаячим b(i) - число бинарных деревьев из i вершин. Тогда следуя рекурсивному определению дерева, можно написать
b(n)=b(0)b(n-1) +b(1)b(n-2) +b(2)b(n-3) +...+b(n-1)b(0)
Рекомендуем скачать другие рефераты по теме: банк курсовых работ бесплатно, отчет по практике.
Предыдущая страница реферата | 1 2 3 4 5 | Следующая страница реферата