Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Программа 5.14 Рекурсивный обход дерева
Деревья и их обход
Деревья – это математические абстракции, играющие огромную роль при разработке и анализе алгоритмов, поскольку - Мы используем деревья для описания динамических свойств алгоритмов; - Мы строим и используем явные структуры данных, которые являются конкретными реализациями деревьев. Мы часто встречаемся с деревьями в повседневной жизни – это основное понятие хорошо знакомо. Например, многие люди отслеживают предков и наследников с помощью генеалогического дерева; как будет показано, значительная часть терминов заимствована именно из этой области применения. Ещё один пример – организация спортивных турниров; среди прочих, в исследовании этого применения принял участие Льюис Кэрролл. В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение отличается иерархическим разделением, характерным для алгоритмов типа “разделяй и властвуй”. Четвёртым примером служит дерево синтаксического разложения предложения английского (или любого другого языка) на составляющие его части; такое дерево близко связано с обработкой компьютерных языков. Применительно к компьютерам, одно из наиболее известных применений структур деревьев — для организации файловых систем. Файлы хранятся в каталогах (иногда называемых также папками), которые рекурсивно определяются как последовательности каталогов и файлов. Это рекурсивное определение снова отражает естественное рекурсивное разбиение на составляющие и идентично определению определенного типа дерева. Существует множество различных типов деревьев, и важно понимать различие • Деревья • Деревья с корнем • Упорядоченные деревья • М-арные и бинарные деревья После этого неформального рассмотрения мы перейдем к формальным определениям и рассмотрим представления и приложения. Дерево (tree) — это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (vertex) — это простой объект (называемый также узлом (node)), который может иметь имя и содержать другую связанную с ним информацию; ребро (edge) — это связь между двумя вершинами. Путь (path) в дереве — это список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева. Определяющее свойство дерева — существование только одного пути, соединяющего любые два узла. Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, мы имеем граф, а не дерево. Несвязанный набор деревьев называется бором (forest). Дерево с корнем (единственным,rooted) — это дерево, в котором один узел назначен корнем (root) дерева. В области компьютеров термин дерево обычно применяется Существует только один путь между корнем и каждым из других узлов дерева. В определенных приложениях способ упорядочения дочерних узлов каждого узла Если каждый узел должен иметь конкретное количество дочерних узлов, появляющихся в конкретном порядке, мы имеем М-арное дерево. В таком дереве часто можно определить специальные внешние узлы, которые не имеют дочерних узлов. Тогда Все это общая терминология. Далее рассматриваются формальные определения, • бинарные и M-арные деревья • упорядоченные деревья • деревья с корнем • свободные деревья Начав с наиболее характерной абстрактной структуры, мы должны быть в состоянии подробно рассмотреть конкретные представления, как станет понятно из дальнейшего изложения. Определение 5. 1 Бинарное дерево — это либо внешний узел, либо внутренний узел, связанный с парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла. Из этого определения становится понятно, что сами деревья - абстрактное математическое понятие. При работе с компьютерными представлениями мы работаем struct node {Item item; node *l, *r;} typedef node * link; что представляет собой всего лишь код С++ для определения 5.1. Узлы состоят из элементов и пар указателей на узлы, и указатели на узлы называются также связями Это стандартное представление позволяет построить эффективную реализацию • чаще всего мы используем представление с двумя связями; • мы используем деревья для реализации АОТ более высокого уровня, и хотим • мы работаем с алгоритмами, эффективность которых зависит от конкретного По этим же причинам мы используем уже знакомые конкретные представления Анализируя связные списки, мы начали рассмотрение с элементарных операций Определение 5.2 М-арное дерево — это внешний узел, либо внутренний узел, связанный с упорядоченной последовательностью М деревьев, которые также являются М-ар- Обычно узлы в М-арных деревьях представляются либо в виде структур с М именованными связями (как в бинарных деревьях), либо в виде массивов М связей. В остальных случаях использование массивов для хранения связей вполне подходит, поскольку значение М фиксировано, хотя, как будет показано, при использовании такого представления особое внимание потребуется уделить интенсивному использованию памяти. Определение 5.3 Дерево (также называемое упорядоченным деревом) — это узел (называемый корнем), связанный с последовательностью несвязанных деревьев. Такая последовательность называется бором. Различие между упорядоченными деревьями и М-арными деревьями состоит в Поскольку каждый узел в упорядоченном дереве может иметь любое количество Лемма 5.4 Существует однозначное соответствие между бинарными деревьями и упорядоченными борами. Любой бор можно представить в виде бинарного дерева, сделав левую связь каждого узла указывающей на его левый дочерний узел, а правую связь каждого узла — указывающей на родственный узел, расположенный справа. Определение 5.4 Дерево с корнем (или неупорядоченное дерево) — это узел (называемый корнем), связанный с множественным набором деревьев с корнем. (Такой множественный набор называется неупорядоченным бором.) Неупорядоченное дерево можно было бы представить в компьютере упорядоченным деревом; при этом приходится признать, что несколько различных упорядоченных деревьев могут представлять одно и то же неупорядоченное дерево. Действительно, обратная задача определения того, представляют ли два различные упорядоченные дерева одно и то же неупорядоченное дерево (задача изоморфизма дерева) трудно подается решению. Наиболее общим типом деревьев является дерево, в котором не выделен ни один корневой узел. Например, основные деревья, полученные в результате работы алгоритмов связности из главы 1, обладают этим свойством. Для правильного определения деревьев без корня, неупорядоченных деревьев и свободных деревьев потребуется начать с определения графов (graphsз). Определение 5.5 Граф — это набор узлов с набором ребер, которые соединяют пары отдельных узлов (причем любую пару узлов соединяет только одно ребро). Представление упорядоченного дерева за счет поддержания связного списка дочерних узлов каждого узла эквивалентно представлению его в виде двоичного дерева. На схеме справа вверху показано представление в виде связного списка дочерних узлов для дерева, показанного слева вверху; при этом список реализован в правых связях узлов, а левая связь каждого узла указывает на первый узел в связном списке его дочерних узлов. На схеме справа внизу приведена несколько измененная версия верхней схемы; она представляет бинарное дерево, изображенное слева внизу. Таким образом, бинарное дерево можно рассматривать в качестве представления дерева. Представьте себе, что перемещаетесь вдоль ребра от одного какого-либо узла до другого, затем от этого узла к следующему и т.д. Последовательность ребер, ведущих одного узла до другого, когда ни один узел не посещается дважды, называется простым путем. Граф является связным (connected), если существует простой путь, связывающий любую пару узлов. Простой путь, у которого первый и последний узел совпадают, называется циклом (сус1е). Каждое дерево является графом; а какие же графы являются деревьями? Граф считается деревом, если он удовлетворяет любому из следующих четырех условий: - Только один простой путь соединяет каждую пару вершин в графе. Обход дерева Когда количество внешних узлов является степенью 2, все внешние узлы в полном бинарном дереве располагаются наодном уровне. В противном случае • Прямой обход (сверху вниз), при котором мы посещаем узел, а затем левое и правое поддеревья • Поперечный обход (слева направо), при котором мы посещаем левое поддерево, • Обратный обход (снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел. Эти методы можно легко реализовать с помощью рекурсивной программы, как Traverse E Visit E Traverse D Visit D Traverse B Visit B Traverse A Visit A Traverse * Traverse * Traverse C Visit C Traverse * Traverse * Traverse * Traverse H Visit H Traverse F Visit F Traverse * Traverse G Visit G Traverse * Traverse * Traverse * Описанная в предыдущем абзаце схема является концептуальной, охватывающей Деревья и их обход
Деревья – это математические абстракции, играющие огромную роль при разработке и анализе алгоритмов, поскольку - Мы используем деревья для описания динамических свойств алгоритмов; - Мы строим и используем явные структуры данных, которые являются конкретными реализациями деревьев. Мы часто встречаемся с деревьями в повседневной жизни – это основное понятие хорошо знакомо. Например, многие люди отслеживают предков и наследников с помощью генеалогического дерева; как будет показано, значительная часть терминов заимствована именно из этой области применения. Ещё один пример – организация спортивных турниров; среди прочих, в исследовании этого применения принял участие Льюис Кэрролл. В качестве третьего примера можно привести организационную диаграмму большой корпорации; это применение отличается иерархическим разделением, характерным для алгоритмов типа “разделяй и властвуй”. Четвёртым примером служит дерево синтаксического разложения предложения английского (или любого другого языка) на составляющие его части; такое дерево близко связано с обработкой компьютерных языков. Применительно к компьютерам, одно из наиболее известных применений структур деревьев — для организации файловых систем. Файлы хранятся в каталогах (иногда называемых также папками), которые рекурсивно определяются как последовательности каталогов и файлов. Это рекурсивное определение снова отражает естественное рекурсивное разбиение на составляющие и идентично определению определенного типа дерева. Существует множество различных типов деревьев, и важно понимать различие • Деревья • Деревья с корнем • Упорядоченные деревья • М-арные и бинарные деревья После этого неформального рассмотрения мы перейдем к формальным определениям и рассмотрим представления и приложения. Дерево (tree) — это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (vertex) — это простой объект (называемый также узлом (node)), который может иметь имя и содержать другую связанную с ним информацию; ребро (edge) — это связь между двумя вершинами. Путь (path) в дереве — это список отдельных вершин, в котором следующие друг за другом вершины соединяются ребрами дерева. Определяющее свойство дерева — существование только одного пути, соединяющего любые два узла. Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, мы имеем граф, а не дерево. Несвязанный набор деревьев называется бором (forest). Дерево с корнем (единственным,rooted) — это дерево, в котором один узел назначен корнем (root) дерева. В области компьютеров термин дерево обычно применяется Существует только один путь между корнем и каждым из других узлов дерева. В определенных приложениях способ упорядочения дочерних узлов каждого узла Если каждый узел должен иметь конкретное количество дочерних узлов, появляющихся в конкретном порядке, мы имеем М-арное дерево. В таком дереве часто можно определить специальные внешние узлы, которые не имеют дочерних узлов. Тогда Все это общая терминология. Далее рассматриваются формальные определения, • бинарные и M-арные деревья • упорядоченные деревья • деревья с корнем • свободные деревья Начав с наиболее характерной абстрактной структуры, мы должны быть в состоянии подробно рассмотреть конкретные представления, как станет понятно из дальнейшего изложения. Определение 5. 1 Бинарное дерево — это либо внешний узел, либо внутренний узел, связанный с парой бинарных деревьев, которые называются левым и правым поддеревьями этого узла. Из этого определения становится понятно, что сами деревья - абстрактное математическое понятие. При работе с компьютерными представлениями мы работаем struct node {Item item; node *l, *r;} typedef node * link; что представляет собой всего лишь код С++ для определения 5.1. Узлы состоят из элементов и пар указателей на узлы, и указатели на узлы называются также связями Это стандартное представление позволяет построить эффективную реализацию • чаще всего мы используем представление с двумя связями; • мы используем деревья для реализации АОТ более высокого уровня, и хотим • мы работаем с алгоритмами, эффективность которых зависит от конкретного По этим же причинам мы используем уже знакомые конкретные представления Анализируя связные списки, мы начали рассмотрение с элементарных операций Определение 5.2 М-арное дерево — это внешний узел, либо внутренний узел, связанный с упорядоченной последовательностью М деревьев, которые также являются М-ар- Обычно узлы в М-арных деревьях представляются либо в виде структур с М именованными связями (как в бинарных деревьях), либо в виде массивов М связей. В остальных случаях использование массивов для хранения связей вполне подходит, поскольку значение М фиксировано, хотя, как будет показано, при использовании такого представления особое внимание потребуется уделить интенсивному использованию памяти. Определение 5.3 Дерево (также называемое упорядоченным деревом) — это узел (называемый корнем), связанный с последовательностью несвязанных деревьев. Такая последовательность называется бором. Различие между упорядоченными деревьями и М-арными деревьями состоит в Поскольку каждый узел в упорядоченном дереве может иметь любое количество Лемма 5.4 Существует однозначное соответствие между бинарными деревьями и упорядоченными борами. Любой бор можно представить в виде бинарного дерева, сделав левую связь каждого узла указывающей на его левый дочерний узел, а правую связь каждого узла — указывающей на родственный узел, расположенный справа. Определение 5.4 Дерево с корнем (или неупорядоченное дерево) — это узел (называемый корнем), связанный с множественным набором деревьев с корнем. (Такой множественный набор называется неупорядоченным бором.) Неупорядоченное дерево можно было бы представить в компьютере упорядоченным деревом; при этом приходится признать, что несколько различных упорядоченных деревьев могут представлять одно и то же неупорядоченное дерево. Действительно, обратная задача определения того, представляют ли два различные упорядоченные дерева одно и то же неупорядоченное дерево (задача изоморфизма дерева) трудно подается решению. Наиболее общим типом деревьев является дерево, в котором не выделен ни один корневой узел. Например, основные деревья, полученные в результате работы алгоритмов связности из главы 1, обладают этим свойством. Для правильного определения деревьев без корня, неупорядоченных деревьев и свободных деревьев потребуется начать с определения графов (graphsз). Определение 5.5 Граф — это набор узлов с набором ребер, которые соединяют пары отдельных узлов (причем любую пару узлов соединяет только одно ребро). Представление упорядоченного дерева за счет поддержания связного списка дочерних узлов каждого узла эквивалентно представлению его в виде двоичного дерева. На схеме справа вверху показано представление в виде связного списка дочерних узлов для дерева, показанного слева вверху; при этом список реализован в правых связях узлов, а левая связь каждого узла указывает на первый узел в связном списке его дочерних узлов. На схеме справа внизу приведена несколько измененная версия верхней схемы; она представляет бинарное дерево, изображенное слева внизу. Таким образом, бинарное дерево можно рассматривать в качестве представления дерева. Представьте себе, что перемещаетесь вдоль ребра от одного какого-либо узла до другого, затем от этого узла к следующему и т.д. Последовательность ребер, ведущих одного узла до другого, когда ни один узел не посещается дважды, называется простым путем. Граф является связным (connected), если существует простой путь, связывающий любую пару узлов. Простой путь, у которого первый и последний узел совпадают, называется циклом (сус1е). Каждое дерево является графом; а какие же графы являются деревьями? Граф считается деревом, если он удовлетворяет любому и
|
||||
Последнее изменение этой страницы: 2016-06-23; просмотров: 370; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.22.249.48 (0.012 с.) |