20510

Орієнтовані і бінарні дерева

Доклад

Информатика, кибернетика и программирование

Бінарне дерево. В програмуванні бінарне дерево – дерево структура даних в якому кожна вершина має не більше двох дітей. Різновиди бінарних дерев Бінарне дерево – таке кореневе дерево в якому кожна вершина має не більше двох дітей. Повне закінчене бінарне дерево – таке бінарне дерево в якому кожна вершина має нуль або двох дітей.

Украинкский

2013-07-25

50.5 KB

4 чел.

  1.  Орієнтовані і бінарні дерева.

Бінарне дерево. Важливим окремим випадком кореневих дерев є бінарні дерева, які широко застосовуються в програмуванні і визначаються як множина вершин, яка має відокремлений корінь та два піддерева (праве та ліве), що не перетинаються, або є пустою множиною вершин (на відміну від звичайного дерева, яке не може бути пустим).

Кожна вершина бінарного дерева, відмінна від кореня, може розглядатися як корінь бінарного піддерева з вершинами, які є досяжними з неї.

В програмуванні бінарне дерево – дерево структура даних, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі бінарних дерев будуються такі структури, як бінарні дерева пошуку та бінарні купи.

Різновиди бінарних дерев 

Бінарне дерево – таке кореневе дерево, в якому кожна вершина має не більше двох дітей.

Повне (закінчене) бінарне дерево – таке бінарне дерево, в якому кожна вершина має нуль або двох дітей.

Ідеальне бінарне дерево – це таке повне бінарне дерево, в якому листя (вершини без дітей) лежать на однаковій глибині (відстані від кореня).

Бінарне дерево на кожному -му рівні має від 1 до  вершин.

Реалізація бінарного дерева.

Кожна вершина містить вказівники на праву та ліву дитину ( left та right)

Існують декілька варіантів конструювання бінарних дерев в залежності від задач, які вирішуються цими структурами та можливостей тої чи іншої мови програмування. Реалізація з використанням вказівників передбачає зберігання в кожній вершині дерева  разом з даними двох полів з вказівниками (правим та лівим)  та  на відповідних дітей цієї вершини.

Модифікована реалізація бінарного дерева.

Кожна вершина містить також вказівник на батьківську вершину

Також іноді додається вказівник  на батьківську вершину. Це виявляється корисним, коли необхідний швидкий доступ до батьківської вершини та спрощує деякі алгоритми. Іноді достатньо тільки вказівника на батьківську вершину. Взагалі будь-яке орієнтоване дерево можна описати, знаючи тільки зв’ язки від дітей до батьківської вершини. Деякі різновиди бінарних дерев (наприклад, червоно-чорні дерева або), вимагають збереження в вершинах і деякої додаткової інформації. Якщо у вершини відсутня одна чи обидві дитини, відповідні вказівники ініціалізуються спеціальними "пустими" значеннями.

Орієнтоване дерево -  — (мульти) граф, ребрам якого присвоєно напрямок. Орієнтовані ребра називаються також дугами, а в деяких джерелах (Оре) і просто ребрами.

Формально, орграф D = (V, E) є множина E впорядкованих пар вершин .

Дуга {u, v} інцидентна до вершин u і v. При цьому говорять, що u — початкова вершина дуги, а v — кінцева вершина.

Орграф, отриманий з простого графа орієнтацією ребер, називається орієнтованим. На відміну від останнього, у довільного простого орграфа дві вершини можуть з'єднуватися двома різноорієнтованими дугами.

Орієнтований повний граф називається турніром.



Маршрутом орграфа називають послідовність вершин і дуг, виду (вершини можуть повторюватися). Довжина маршруту — кількість дуг у ньому.

Шлях — маршрут орграфа без повторюваних дуг, простий шлях — без повторюваних вершин. Якщо існує шлях з однієї вершини в іншу, то друга вершина досяжна з першої.

Контур — замкнений шлях.

Для напівмаршруту знімається обмеження на напрямок дуг, аналогічно визначаються напівшлях і напівконтур.

Орграф сильно зв'язний, або просто сильний, якщо всі його вершини взаємно досяжні; Односторонньо зв'язний, або простоодносторонній якщо для будь-яких двох вершин, принаймні одна досяжна з іншою; Слабо зв'язний, або просто слабкий, якщо при ігноруванні напрямів дуг виходить зв'язний (мульти)граф;

Максимальний сильний підграф називається сильною компонентно. одностороння компонента і слабка компонента визначаються аналогічно .

Конденсацією орграфа D називають орграф D*, вершинами якого служать сильні компоненти D, а дуга в D* показує наявність хоча б однієї дуги між вершинами, що входять у відповідні компоненти.


 

А также другие работы, которые могут Вас заинтересовать

48873. Разработать печатный узел устройства с помощью пакета программ САПР P-CAD 2006 1.02 MB
  Чтобы создать новую библиотеку необходимо выполнить следующую последовательность действий: Выбрать команду Librry New. Для подготовки редактора к работе необходимо выполнить следующие операции: Выбрать команду Options Configure и в появившемся окне установить размер рабочего поля формата А4. Выбрать команду View Snp to grid для привязки курсора к узлам сетки. Выбрать команду Options Grids и установить шаг сетки равный 1.
48874. Разработка участка топливной аппаратуры на 628 автомобилей МАЗ-53371 2.93 MB
  Расчет годового объема работ Расчет годового объема работ по ТО ТР и самообслуживанию. Разработка участка топливной аппаратуры на 628 автомобилей МАЗ 53371 Лит.
48875. Определение видовой принадлежности грибов 717.5 KB
  Обучение нейросети. Применение нейросети для определения вида грибов. Искусственные нейронные сети прочно вошли в нашу жизнь и в настоящее время широко используются при решении самых разных задач и активно применяются там где обычные алгоритмические решения оказываются неэффективными или вовсе невозможными. Нейронные сети – исключительно мощный метод моделирования позволяющий воспроизводить чрезвычайно сложные зависимости.
48876. ПРОГНОЗИРОВАНИЕ БУКМЕКЕРСКИХ КОЭФФИЦИЕНТОВ 108.5 KB
  Но букмекерам приходится решать несколько иную задачу им необходимо оценить вероятность каждого исхода матча победу поражение какойлибо команды или ничейный результат и по итогам этой оценки определить какую сумму они готовы выплачивать победителю в случае если тот правильно сумел предугадать результат. Задача состоит в том чтобы с помощью нейронных сетей определить коэффициенты на матчи с возможными исходами: победа первой команды победа второй команды ничья. Ниже приводится их список: количество выигранных в прошлом сезоне...
48877. Использование нейронных сетей в банковском деле 398 KB
  Искусственные нейронные сети Нейросети в банковском деле Глава Постановка задачи Для решения поставленной задачи будем использовать персептрон основанный на нейронной сети с 14ю входами с 1 выходным и с двумя скрытыми слоями. Нейронные сети и нейрокомпьютеры это одно из направлений компьютерной индустрии в основе которого лежит идея создания искусственных интеллектуальных устройств по образу и подобию человеческого мозга.
48880. Прогнозирование доходности московского рынка жилой недвижимости 235 KB
  Задачей данной работы является прогнозирование доходности жилой недвижимости Москвы. Рынок недвижимости практически во всех странах является одним из наиболее важных секторов экономики. Состояние рынка недвижимости отражает состояние экономики страны в целом риски экономики и ее возможности.
48881. Радіоелектронні пристрої системи та комплекси. Методичні вказівки 977.5 KB
  Список предметних скорочень АМ – амплітудна модуляція; АССЗ – аналогова система стільникового зв’язку; БПС – буферний підсилювач сигналу; ГКН – генератор керований напругою; ГОЧ – генератор опорної напруги; ДВЧ – дільник високої частоти; ДКМХ – декаметрові хвилі; ДСТУ – Державний стандарт України; ЄСКД – Єдина система конструкторської документації; КГ – кварцовий генератор; КІМ – кодовоімпульсна модуляція; МХ – метрові хвилі; НВЧ – надвисокі частоти; ОМ – односмугова модуляція; ПБТЗ – передавач базової станції транкінгового зв’язку; ПЗКД –...