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* показує наявність хоча б однієї дуги між вершинами, що входять у відповідні компоненти.


 

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

76894. Медиальная петля, состав волокон, положение на срезах мозга 180.14 KB
  Тела первых псевдоуниполярных нейронов бульботаламического пути находятся в спинномозговых узлах а их периферические отростки в составе спинальных нервов подходят к опорнодвигательным органам в которых заканчиваются рецепторами. Центральные отростки первых нейронов вступают в синаптические контакты с телами вторых нейронов которые находятся в тонком и клиновидном ядрах продолговатого мозга. Аксоны вторых нейронов образуют в продолговатом мозге дугообразные волокна: внутренние и наружные. Аксоны вторых нейронов участвующих в образовании...
76895. Двигательные проводящие пирамидные и экстрапирамидные пути 182.52 KB
  Первые нейроны представлены большими пирамидными клетками коры мозга. Вторые нейроны находятся в ядрах мозгового ствола и передних рогах спинного мозга а их аксоны заканчиваются в органах опорнодвигательного аппарата. Первый проходит от нейронов прецентральной извилины до двигательных нейронов сосредоточенных в ядрах ствола мозга это кортикоядерный путь. Два других тракта: кортикоспинальные передний и боковой идут от прецентральной извилины до ядер передних рогов спинного мозга.
76896. Ретикулярная формация 180.5 KB
  Далее проходит через мозговой ствол и его составляющие продолговатый мозг мост ножки мозга и четверохолмие зрительные бугры и достигает базальных ядер и коры конечного мозга. Крупные нейроны сосредотачиваются в ядрах ретикулярной формации: субталамическом красном черной субстанции мостовом ретикулярных ядрах продолговатого мозга и др. Причем один отросток имеет восходящее направление вплоть до клеток коры другой нисходящее к нейронам мозжечка спинного мозга.
76897. Оболочки и пространства мозга 183.61 KB
  В отверстиях основания твердая оболочка окружает и фиксирует проходящие через них сосуды и нервы. Паутинная оболочка состоит из волокнистой соединительной ткани покрытой эндотелием. Вблизи менингеальных синусов паутинная оболочка образует эти самые грануляции врастающие в просвет синусов и вен костного диплоетического вещества.
76898. Спинальные нервы 181.13 KB
  Спинномозговой нерв смешанный по составу волокон образуется: передним корешком двигательным из длинных отростков нейронов расположенных в ядрах передних рогов спинного мозга; отростки нейронов в составе нервов достигают органов где образуют нервные окончания исполнительного типа эффекторы; задним корешком и спинальным узлом дендриты псевдоуниполярных клеток которого составляют задний корешок и достигают задних рогов спинного мозга а длинные отростки этих клеток входят в состав спинальных нервов и их производных образуя в...
76899. Шейное сплетение 179.82 KB
  Ветви и области иннервации. Ветви подразделяются на кожные мышечные и смешанные короткие и длинные. В каждом сплетении правом и левом имеются следующие ветви.
76900. Плечевое сплетение. Ветви надключичной части плечевого сплетения, области иннервации 179.65 KB
  Источниками образования плечевого сплетения являются передние ветви четырех нижних шейных и 12го грудных спинномозговых нервов. Дорсальный нерв лопатки начинается из передней ветви V шейного спинального нерва. Подключичный нерв из пятой передней ветви проходит кпереди от подключичной артерии и заканчивается в одноименной мышце.
76901. Подключичная часть плечевого сплетения 183.27 KB
  Она имеет короткие нервы: дорсальный лопаточный длинный грудной подключичный над и подлопаточные грудоспинной которые иннервируют кожу мышцы шеи груди и надплечья. Нервные стволы сплетения вступившие в подмышечную яму обозначаются как подключичная часть которая окружает подмышечную артерию с трех сторон подковообразно и делится на медиальный латеральный и задний пучки дающие начало длинным и коротким нервам руки. Из латерального пучка C V – C VIII начинаются латеральный грудной мышечнокожный нервы и латеральный корешок...
76902. Межреберные нервы, их ветви и области иннервации 180.98 KB
  Передние ветви грудных спинномозговых нервов образуют 11 пар межреберных нервов и 12ю пару подреберные нервы. Нервы в межреберном промежутке располагаются вместе с задними межреберными сосудами. Межреберные нервы ярко выражают метамерное расположение и сегментарную иннервацию кожи и мышц груди и живота реберной плевры и париетальной брюшины.