20510

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

Доклад

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

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

Украинкский

2013-07-25

50.5 KB

6 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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


 

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

30180. Анализ земляники садовой выращеной на базе плодового питомника ООО «Полисад» в городе Горки Могилевской области 1.13 MB
  Первые крупноплодные сорта земляники появились в 1840 году. Через 20 лет эти сорта были завезены в Казань на ферму земледельческого училища. Растения преимущественно двудомные встречаются сорта с обоеполыми цветками. В диком состоянии этот вид не встречается к нему принадлежат все сорта крупноплодной садовой земляники которые ныне культивируются.
30182. Установление специфики юридической ответственности органов местного самоуправления 428.5 KB
  Ответственность органов местного самоуправления выступает важным элементом их правового статуса гарантией качественной работы и добросовестного осуществления своих полномочий. Предназначение конституционноправовой ответственности заключается в охране конституционного строя основных прав и свобод граждан в обеспечении нормального порядка осуществления публичной власти в следовании органов местного самоуправления предписаниям действующего законодательства в предупреждении превенции посягательств на порядок осуществления...
30183. Повышения эффективности использования строительных машин, увеличение срока их службы и надежности в работе 897.6 KB
  Рост парка машин позволил в значительной степени механизировать труд работников в строительстве. Уровень его механизации достиг 80%. Машинами выполняются почти все основные виды строительно-монтажных работ. В этих условиях своевременность и высокое качество сооружения строительных объектов в большой степени зависят от уровня работоспособности машин. Чем он выше, тем больше гарантий в том, что объекты будут построены в установленные сроки и качественно.
30184. Пропозиції щодо поліпшення співробітництва між Україною та ЄС у виробничому секторі 114.5 KB
  Економічне становище регіону, створення належних умов для життя і праці його населення залежить від розвитку виробничої сфери. Виробнича сфера виступає основою для задоволення людських потреб. Потреби, в свою чергу, відіграють роль стимуляторів діяльності людей.
30185. Разработка системы управления электроприводом листоправильной машины, учитывающий переменность статического момента нагрузки и момента инерции, с целью повышения энергетической эффективности стана11×280×2300 3.84 MB
  передачи от двигателя к валку отн. От первого двигателя 24M1 по ходу металла приводится пять правильных валков три верхних и два нижних находящихся ближе к входу листоправильной машины; от второго двигателя 24M2 остальные шесть валков №6№11. Двигатели предназначены для работы от преобразователей частоты и оснащены каждый датчиком импульсов 24BN1 24BN2 контроль скорости вентилятором обдува с электроприводом двигатели 24M3 24M4 а также датчиками контроля температуры в обмотках KTY 84130 1 шт и подшипниках...
30186. Разработка проекта межевания земельных участков на землях бывшего колхоза “Россия” Каширского района Воронежской области 3.42 MB
  Земельный кодекс Российской Федерации от 25.10.2001 г. №136-ВЗ является головным отраслевым законом, обладающим приоритетом в регулировании земельных отношений. Кодекс создает правовые гарантии провозглашенных в Конституции РФ земельных прав граждан; устанавливает приоритет охраны земли перед использованием в качестве недвижимости; приоритет охраны жизни и здоровья человека при решении вопроса о затратах
30187. Динамика роста и накопление сухого вещества по фазам развития растений яровой пшеницы в зависимости от условий питания и применения удобрений 80.51 KB
  Народнохозяйственное значение яровой пшеницы. Морфологические и биологические особенности яровой пшеницы. Влияние удобрений на урожайность и качество зерна яровой пшеницы яровых зерновых культур. Динамика роста и накопление сухого вещества по фазам развития растений яровой пшеницы в зависимости от условий питания и применения удобрений.
30188. Развитие композиционных умений учащихся 6-х классов средствами декоративного натюрморта в технике гуашь 1.13 MB
  Одной из основных задач образования является всестороннее созревание личности ребенка, а так же эстетическое воспитание подрастающего поколения. Эстетическое воспитание - это сложный и продолжительный процесс, дети приобретают первые художественные впечатления, изучая различные виды художественной деятельности. Изобразительная деятельность - специфическое, образное постижение действительности, которое может идти всевозможными путями.