20510

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

Доклад

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

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

Украинкский

2013-07-25

50.5 KB

5 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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


 

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

82520. Задания, направленные на развитие логического мышления младших школьников с ЗПР 61.5 KB
  Примеры такого анализа: Данное упражнение можно использовать на уроках математики. Данное упражнение рекомендуется использовать на уроках математики ознакомления с окружающим миром а также труда 2. Упражнение можно использовать на уроках математики. Это задание рекомендуется использовать на уроках математики ознакомления с окружающим миром и труда.
82521. Развитие мышления у детей с ЗПР младшего школьного возраста 35.5 KB
  Особый интерес представляет метод обучения детей модельному конструированию разработанный А. Важным при таком способе обучения конструированию является то что мыслительные процессы детей приобретают опосредованный характер нежели при конструировании по образцу. Для этого необходим достаточно высокий уровень абстрагирования что дает возможность формированию у детей специфических способов соотнесения определенных свойств условий с соответствующими свойствами постройки.
82522. Развитие мышления у младших школьников с ОНР 4.26 MB
  Отгадывание ребусов: отгадать слово из двух предлогов: найти в слове квас три предлога: Цель: развитие словеснологического мышления Установление простых аналогий навыков словообразования. Цель: развитие словеснологического мышления устойчивости и концентрации слухового внимания. Задание: определить что пропущено в рассказе: названия предметов предлоги или названия признаков Цель: развитие нагляднообразного мышления.
82523. Методы и приемы развития словесно-логического мышления учащихся с речевой патологией на уроках 83.5 KB
  Инструкция: Я буду говорить слово по звукам слогам а ты запиши его в тетради. а сани солома зэркало дворэц б первый слогпу третий слог вик второй слог хо; первый слог пу третий слог ка второй слогшин второй слог шок первый слог пу третий слог ка второй слог пуш первый слого Дополнительное задание: подчеркнуть лишнее слово. первый слог са второй слог мо третий слог кат третий слог ле второй слог то первый слог вер первый слог са третий слог ник...
82524. Дидактические игры и упражнения, направленные на развитие мышления у детей с умственной отсталостью дошкольного возраста 100.5 KB
  Педагог просит ребенка отнести на один стул такие указательный жест а на другой такие. Педагог дает одному из детей коробку с круглой прорезью а другому с квадратной и ставит условие: отобрать сразу все что можно протолкнуть в данную коробку. Если он выбирает правильно например шары но берет не все а только один или два шара педагог напоминает ему что нужно взять все такие указывает на шары. После того как дети отберут и бросят в прорези коробок нужные формы педагог подводит итог: Правильно Таня собрала все шары и...
82525. Игры для развития мышления и воображения у детей дошкольного возраста с нарушением слуха 88.5 KB
  Педагог просит: Достань тележку. Если ребенок вытянул тесьму то педагог вставляет ее снова обязательно за экраном. Если все же ребенок не сумел сделать сам педагог медленно показывает. Педагог предлагает детям выложить из своих фишек узоры по картинке.
82526. Развитие мышления на уроках русского языка 96.5 KB
  Ход проведения: детям были даны карточки с нижеприведёнными упражнениями. Ход проведения: на уроке идёт беседа об известных модельерах анализируются модели одежды созданные ими. Ход проведения: детям говорится что им сейчас будут зачитываться слова и они должны в уме переставить буквы наоборот и тут же записать в тетрадь получившийся результат. Ход проведения: на доске зарисовывается схема.
82527. Развитие памяти и мышления у детей с ОВЗ на занятиях по дополнительной образовательной программе «Я все умею делать сам, что не умею, научусь!» 38 KB
  Ведущий: Дети сейчас я прочитаю вам стихотворение Корнея Чуковского Путаница. Ведущий перед игрой проводит короткую беседу уточняя понимание детьми слов профессия действия. Ведущий. Ведущий.