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


 

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

46117. Значение изобразительной деятельности в воспитании детей и коррекции у них речевых нарушений 14 KB
  Включение речи в познавательные процессы восприятие представление воображение без которых не может развиваться изобразительная деятельность оказывает положительное влияние на развитие личности ребенка. В свою очередь хорошо организованные занятия рисованием представляют сильное средство развития речи.Развитие речи в процессе изобразительной деятельности осуществляется в нескольких направлениях: вопервых происходит обогащение словаря вовторых осуществляется становление и развитие речи как средства общения втретьих совершенствуется...
46118. Психологические и лингвистические основы теорий речевой деятельности. Язык, речь, речевая деятельность 13.5 KB
  Язык речь речевая деятельность. предмет речевая деятельность как целое и закономерности ее комплексного моделирования. Речевая деятельность акт. Речевая деятельность имеет предметное содержание определенную структурную организациювнешнюю и внутреннюю подчиняется общефункционнальным психическим механизмамвнимание память Язык = речь Щерба: троякий аспект языкового явления эксперимент в языкознании: сам процесс речевой деятельностипроцесс; языковая системакод; языковой материал.
46119. Современные принципы анализа высших психических функций. Речь в системе психических процессов. Модели порождения речевого высказывания 10.5 KB
  Стахостическая модель Миллер Хомский опирается на идею вероятности появления единицы на основе уже использованной. Модель Чарльза Осгуда Модель Хомского трансформирования. Модель Миллера Модель Т.
46120. Методика логопедического обследования ребёнка с фонетико-фонематическим недоразвитием речи 15.5 KB
  Обследование детей осуществляет логопед Логопедическое обследование ребёнка с ФФН проходит в несколько этапов: Подготовительный. Основной непосредственно обследование. Само обследование: артикуляционный аппарат и артикуляционная моторика; звукопроизношение; фонематическое восприятие обследование дифференциации звуков и сформированность навыков анализа и синтеза обследование слоговой структуры слова.
46121. Методика логопедического обследования ребёнка с общим недоразвитием речи 24.5 KB
  Методика логопедического обследования ребёнка с общим недоразвитием речи. Необходим анализ взаимодействия между процессом овладения звуковой стороной речи развитием лексического запаса и грамматического строя. Важно определить соотношение развития экспрессивной и импрессивной речи ребенка; выявить компенсирующую роль сохранных звеньев речевойспособности; сопоставить уровень развития языковых средств с актуальным их использованием в речевом общении. Важно выяснить в каком возрасте появились первые слова и каково количественное соотношение...
46122. Методика логопедического обследования заикающегося ребёнка 17 KB
  Из беседы с родителями логопед выясняет наиболее значимые события происшедшие в семье ОБО ВСЕМВСПОМИНАЙ После уточнения сведений о ребенке проводится обследование речи заикающегося и внеречевых процессов оказывающих непосредственное влияние на его речевую деятельность. Проводится исследование его общительности моторики подражательности импрессивной и экспрессивной речи игровой учебной производственной деятельности особенности личности заикающегося.Для исследования речи детей используются картинки книжки со стихами...
46123. Методика логопедического обследования при нарушениях письменной речи 25.5 KB
  Цель обследования: выявление этиологии симптоматики нарушений чтения и письма. Обследование письма. Нарушение письма у детей это особые специфические затруднения которые обусловлены системным недоразвитием определенных сторон речевой деятельности ребенка которое у детей достигших школьного возраста при нормальных умственных способностях и слухе проявляется прежде всего в недостаточной сформированности представлений о звуковом и морфологическом составе слова. Общие методические рекомендации обследованию письма у детей...
46124. Технология развития общей, мелкой моторики рук у детей с нарушениями речи 16 KB
  Коррекция особенностей моторного развития детей направлена на нормализацию мышечного тонуса исправление неправильных поз развитие статической выносливости равновесия упорядоченного темпа движений синхронного взаимодействия между движениями и речью запоминание серии двигательных актов воспитание быстроты реакции на словесные инструкции развитие тонких двигательных координаций необходимых для полноценного становления навыков письма. Этому служат следующие упражнения: сжимать резиновую грушу или теннисный мячик; разгибать и...
46125. Методика развития артикуляционной моторики у детей с речевыми нарушениями 16.5 KB
  Особо можно выделить кончик языка ибоковые края передней и средней частей языка так как от их работы зависит качество звуков. В артикуляционную гимнастику входят упражнения в ходе которых вырабатываются следующие положения кончика языка: опущен за нижние зубы Почистим зубы поднят вверх к альвеолам Маляр Грибок Гармошка. После того как каждое положение будет отработано дается упражнение на переключение с одного положения языка на другое Качели. Средняя часть спинки языка наиболее ограничена в...