Деревья общего вида (не двоичные).

Особенность таких деревьев – заблаговременно неведомое число потомков вершин, что не позволяет объявить в каждой верхушке какое-то разумное количество ссылочных полей.

Подобные деревья употребляются пореже двоичных, но все же есть круг задач, где они нужны. Существует несколько методов описания схожих деревьев, к примеру – представление их через набор двоичных деревьев. Другой метод употребляет понятие Деревья общего вида (не двоичные). сложной списковой структуры. Поначалу создаётся основной линейный перечень, содержащий все верхушки-предки (не терминальные). С каждой родительской верхушкой дополнительно связывается перечень ее потомков.

Начальное недвоичное дерево Представление в виде перечня списков

Так как неважно какая верхушка начального дерева может быть как в главном перечне родителей, так и в перечне потомков, структура Деревья общего вида (не двоичные). частей всех списков должна быть схожей. Любая верхушка в этой структуре обязана иметь информационное поле и два ссылочных поля: указатель на последующий элемент в родительском перечне и указатель на последующий элемент перечня потомков. Зависимо от присутствия верхушки в том либо ином перечне некие поля могут быть пустыми.

TypeTp = ^ TNode Деревья общего вида (не двоичные).;

TNode = record

Inf : ;

NextParent, NextChild : Tp;

end;

В перечнях потомков ссылочное поле NextParent в простом случае просто не употребляется (устанавливается в nil). Как вариант, можно в этом поле хранить указатель на одноименную верхушку в родительском перечне.


Схематично разглядим реализацию главных операций с схожим списковым представлением недвоичных деревьев.

1. Вывод перечня родителей с надлежащими перечнями потомков реализуется двойным Деревья общего вида (не двоичные). циклом: наружный цикл идет по списку родителей, а внутренний позволяет для каждого родителя вывести перечень его потомков

PCurrentParent := pRoot;

While pCurrentParent nil do

Begin

“обработка верхушки pCurrentParent^”;

pCurrentChild := pCurrentParent^.NextChild;

while pCurrentChild nil do

Begin

“обработка верхушки pCurrentChild^”;

pCurrentChild := pCurrentChild^.NextChild;

end;

pCurrentParent := pCurrentParent^.NextParent;

end;

2. Добавление верхушки X как потомка верхушки Y:

· “поиск верхушки Y обходом всех вершин Деревья общего вида (не двоичные).”;

· if “верхушка Y найдена в перечне родителей” then “добавляем X в перечень потомков верхушки Y”;

· if “верхушка Y найдена в перечне потомков” then

ü “добавляем Y в перечень родителей”;

ü “создаем у верхушки Y перечень потомков с верхушкой X”;

3. Удаление верхушки X, если она не корневая для всего дерева:

· “поиск верхушки X обходом всех Деревья общего вида (не двоичные). вершин”;

· if “верхушка X найдена в перечне родителей” then

ü “просмотром всех списков отыскать родителя верхушки X”;

ü “удалить X из перечня потомков”;

ü “к родителю X добавить перечень всех потомков X”;

· if “верхушка X есть исключительно в перечне потомков” then

ü “удалить X из перечня потомков”;

ü if “перечень потомков пуст, то удалить родителя из перечня родителей Деревья общего вида (не двоичные).”;

Представление графов

Граф – это огромное количество однотипных объектов (вершин), некие из которых связаны вместе какими-либо связями (ребрами). Одна связь всегда соединяет только две верхушки (время от времени – верхушку саму с собой). Главные разновидности графов:

· неориентированные (обыденные), в каких важен только сам факт связи 2-ух вершин

· направленные (орграфы), для которых принципиальным является к тому же направление связи вершин

· взвешенные, в Деревья общего вида (не двоичные). каких принципиальной информацией является к тому же степень (величина, вес) связи вершин

Примеры графов различных типов:

обыденный направленный взвешенный

Для описания графа как структуры данных употребляются два метода: матрицы смежностиисписки смежности. 1-ый метод подразумевает внедрение двумерного массива чисел, который для обычных графов заполняется только значениями 0 (нет связи) и 1 (есть связь), а для Деревья общего вида (не двоичные). взвешенного – значениями весов. Для обыденного графа матрица смежности всегда является симметричной относительно главной диагонали, а для орграфа в большинстве случаев эта матрица не симметрична, что отражает одностороннюю направленность связей.

Для рассмотренных выше примеров матрицы смежности будут последующими:

A B C D E
A
B
C
D
E

A Деревья общего вида (не двоичные). B C D E
A
B
C
D
E

A B C D E
A
B
C
D
E

Недочеты данного метода:

· заблаговременно нужно знать хотя бы приблизительное число вершин в графе

· для графов с огромным числом вершин матрица становится очень большой (к примеру 1000*1000 = 1 миллион чисел)

· при малом числе связывающих ребер матрица Деревья общего вида (не двоичные). заполнена в главном нулями

Этих недочетов почти во всем лишен 2-ой метод, основанный на использовании списков смежных вершин. Тут списки содержат ровно столько частей, сколько ребер в графе, и не считая того верхушки и ребра могут добавляться динамически. Перечень смежных вершин представляет собой главный перечень всех вершин и огромное количество вспомогательных списков, содержащих Деревья общего вида (не двоичные). список вершин, связанных с данной. Для рассмотренных выше обыденного графа и нацеленного графа списки смежности будут последующими:

B
A
C
A
D
A
E
A
E
D
C
B
E
D
C
B
A

E
E
A
D
B
E
A
C
B
E
D
C
B Деревья общего вида (не двоичные).
A

Описание схожей сложной списковой структуры производится обыденным образом.

Операции прибавления и удаления по сопоставлению с деревьями имеют последующие варианты:

· добавление новейшей связи (ребра) меж данной парой имеющихся вершин

· добавление новейшей верхушки вкупе со всеми необходимыми связями

· удаление связи (ребра) меж 2-мя верхушками

· удаление верхушки вкупе со всеми ее связями

Добавление нового ребра содержит в Деревья общего вида (не двоичные). себе (на примере обыденного графа):

· получение имен связываемых вершин

· поиск в главном перечне первой связываемой верхушки

· поиск в перечне смежных ей вершин 2-ой связываемой верхушки и или вывод сообщения об ошибке, или добавление в этот перечень нового элемента с именованием 2-ой верхушки

· поиск в главном перечне 2-ой связываемой верхушки

· поиск в перечне смежных Деревья общего вида (не двоичные). ей вершин первой связываемой верхушки и или вывод сообщения об ошибке, или добавление в этот перечень нового элемента с именованием первой верхушки

Добавление новейшей верхушки содержит в себе:

· запрос имени новейшей верхушки совместно с именами всех связываемых с ней вершин

· поиск в главном перечне имени новейшей верхушки и в случае отсутствия ее -добавление в Деревья общего вида (не двоичные). основной перечень

· формирование перечня вершин, смежных вновь добавленной

· поиск в главном перечне всех смежных вершин и добавление в их вспомогательные списки нового элемента с именованием новейшей верхушки

Удаление ребра делается последующим образом:

· запрос имен 2-ух вершин, меж которыми разрывается связь

· поиск в главном перечне каждой из этих вершин

· поиск в каждом из 2-ух вспомогательных списков имени Деревья общего вида (не двоичные). примыкающей верхушки и удаление соответственного элемента

Удаление верхушки делается последующим образом:

· запрос имени удаляемой верхушки

· поиск ее в главном перечне

· просмотр вспомогательного перечня удаляемой верхушки, для каждого элемента которого:

o поиск смежной верхушки в главном перечне и удаление из ее вспомогательного перечня элемента, соответственного удаляемой верхушке

o удаление самого элемента из вспомогательного Деревья общего вида (не двоичные). перечня

· удаление верхушки из основного перечня

При обработке графов нередко приходится делать обход всех его вершин. Правила обхода графов похожи на обход деревьев. Есть два главных правила обхода, известные как поиск в глубину и поиск в ширину.

Поиск в глубину употребляет две структуры – стек для запоминания еще не обработанных вершин и перечень для запоминания уже обработанных. Поиск производится последующим Деревья общего вида (не двоичные). образом:

· задать стартовую верхушку (аналог корневой верхушки при обходе дерева)

· обработать стартовую верхушку и включить ее во вспомогательный перечень обработанных вершин

· включить в стек все верхушки, смежные со стартовой

· организовать цикл по условию опустошения стека и снутри цикла выполнить:

o извлечь из стека еще одну верхушку

o проверить по вспомогательному Деревья общего вида (не двоичные). списку обработанность этой верхушки

o если верхушка уже обработана, то извлечь из стека последующую верхушку

o если верхушка еще не обработана, то обработать ее и поместить в перечень обработанных вершин

o просмотреть весь перечень смежных с нею вершин и поместить в стек все еще не обработанные верхушки

К примеру, для рассмотренного выше обыденного Деревья общего вида (не двоичные). графа получим:

· пусть стартовая верхушка – B

· включаем B в перечень обработанных вершин: перечень = (В)

· помещаем в стек смежные с В верхушки, т.е. A и E: стек = (А, Е)

· извлекаем из стека верхушку E: стек = (А)

· т.к. E нет в перечне обработанных вершин, то обрабатываем ее и помещаем в Деревья общего вида (не двоичные). перечень: перечень = (В, Е)

· смежные с E верхушки – это A и B, но B уже обработана, потому помещаем в стек только верхушку А: стек = (А, А)

· извлекаем из стека верхушку А: стек = (А)

· т.к. Ан нет в перечне обработанных вершин, то помещаем ее туда: перечень = (В, Е, А)

· смежные Деревья общего вида (не двоичные). с А верхушки – это B, C, D, E, из которых B и E уже обработаны, потому помещаем в стек C и D: стек = (A, C, D)

· извлекаем из стека верхушку D: стек = (A, C)

· т.к. D не обработана, то помещаем ее в перечень: перечень = (B, E, A, D)

· смежные с Деревья общего вида (не двоичные). D верхушки – это А и С, из которых А уже обработана, потому помещаем в стек верхушку С: стек = (А, С, С)

· извлекаем из стека верхушку С: стек = (А, С)

· т.к. С не обработана, помещаем ее в перечень: перечень = (B, E, A, D, C)

· смежные с Деревья общего вида (не двоичные). С верхушки – это A и D, но они обе уже обработаны, потому в стек ничего не заносим

· извлекаем из стека С, но она уже обработана

· извлекаем из стека А, но она тоже уже обработана

· т.к. стек стал пустым, то завершаем обход с результатом (B, E, A, D, C)

Поиск в ширину работает мало по другому Деревья общего вида (не двоичные).: поначалу обрабатываются все верхушки, смежные с текущей, а только позже – их потомки. Заместо стека для запоминания еще не обработанных вершин употребляется очередь. Последовательность действий:

· задать стартовую верхушку (аналог корневой верхушки при обходе дерева)

· обработать стартовую верхушку и включить ее во вспомогательный перечень обработанных вершин

· включить в очередь все верхушки, смежные со Деревья общего вида (не двоичные). стартовой

· организовать цикл по условию опустошения очереди и снутри цикла выполнить:

o извлечь из очереди еще одну верхушку

o проверить по вспомогательному списку обработанность этой верхушки

o если верхушка уже обработана, то извлечь из очереди последующую верхушку

o если верхушка еще не обработана, то обработать ее и поместить в перечень обработанных вершин

o просмотреть весь перечень Деревья общего вида (не двоичные). смежных с нею вершин и поместить в очередь все еще не обработанные верхушки

Тот же что и ранее пример даст последующий итог:

· пусть стартовая верхушка – B

· включаем B в перечень обработанных вершин: перечень = (В)

· помещаем в очередь смежные с В верхушки, т.е. A и E: очередь = (А, Е)

· извлекаем Деревья общего вида (не двоичные). из очереди верхушку А: очередь = (Е)

· т.к. она не обработана, добавляем ее в перечень: перечень = (В, А)

· смежные с А верхушки – это B, C, D и E, помещаем в очередь верхушки C, D и E: очередь = (E, C, D, E)

· извлекаем из очереди верхушку Е: очередь = (C, D, E Деревья общего вида (не двоичные).)

· т.к. Е не обработана, помещаем ее в перечень: перечень = (B, A, E), т.е. сначала обработаны обе смежные с В верхушки

· смежные с Е верхушки – это А и В, но обе они уже обработаны, потому очередь новыми верхушками не дополняется

· извлекаем из очереди верхушку С: очередь = (D, E)

· т.к Деревья общего вида (не двоичные).. С не обработана, то помещаем ее в перечень: перечень = (B, A, E, С)

· смежные с С верхушки – это А и D, помещаем в очередь только D: очередь = (D, E, D)

· извлекаем из очереди верхушку D: очередь = (E, D)

· т.к. D не обработана, помещаем ее в перечень: перечень = (B, A Деревья общего вида (не двоичные)., E, С, D)

· смежные с D верхушки – это А и С, но обе они обработаны, потому очередь не дополняется

· извлекаем из очереди верхушку Е, но она уже обработана: очередь = (D)

· извлекаем из очереди верхушку D, но она уже обработана и т.к. очередь становится пустой, то поиск завершается Деревья общего вида (не двоичные). с результатом (B, A, E, С, D), что отличается от поиска в глубину.

В заключение отметим несколько более нередко встречающихся задач на графах:

· отыскать путь меньшей (большей) длины меж 2-мя данными верхушками

· выделить из графа дерево, имеющее меньший суммарный вес ребер (кратчайшее покрывающее дерево)

· присвоить каждой верхушке графа цвет таким макаром Деревья общего вида (не двоичные)., чтоб не было ни одной пары смежных вершин, имеющих однообразный цвет, и при всем этом число применяемых цветов было бы наименьшим (задачка раскраски графа)

· отыскать в графе таковой путь, который проходит по всем верхушкам ровно по 1 разу и имеет при всем этом меньшую суммарную длину (задачка кочевого торговца либо Деревья общего вида (не двоичные). коммивояжера).

Практические задания

Задание 1.Воплотить главные операции с недвоичными деревьями, представленными при помощи перечня родителей и потомков. Будем считать, что изначальное дерево содержит единственную корневую верхушку. Нужно воплотить последующие операции:

· добавление новейшей верхушки как потомка данной верхушки

· удаление данной верхушки

· вывод всех вершин с указанием родительских связей

· поиск данной верхушки

Требования к подпрограммам и Деревья общего вида (не двоичные). главной программке – стандартные.

Задание 2. Воплотить главные операции с ординарными графами с внедрением матричного и спискового представлений:

· формирование матрицы смежности

· преобразование матрицы смежности в перечень смежности

· формирование перечня смежности

· преобразование перечня смежности в матрицу смежности

· добавление нового ребра

· удаление данного ребра

· добавление новейшей верхушки

· удаление данной верхушки

· обход графа в глубину

· обход графа в ширину

Требования к подпрограммам и главной Деревья общего вида (не двоичные). программке – стандартные.

7.6. Контрольные вопросы по теме

1. Какие задачи появляются при использовании деревьев поиска?

2. Как оказывает влияние на структуру дерева поиска различный порядок поступления одних и тех же входных ключей?

3. Почему при построении дерева поиска принципиально управлять его структурой?

4. Какие деревья именуются АВЛ-сбалансированными?

5. Как связаны понятия “совершенно равновесное дерево Деревья общего вида (не двоичные).” и “АВЛ-сбалансированное дерево”?

6. Приведите примеры совершенно равновесного, АВЛ-сбалансированного и не-АВЛ-сбалансированного деревьев.

7. Какой параметр употребляется для реализации АВЛ-сбалансированных деревьев?

8. По какому методу производится АВЛ-балансировка дерева при добавлении верхушки?

9. Какие ситуации вероятны по мере надобности балансировки некого поддерева?

10. Как производится однократный поворот?

11. Как производится Деревья общего вида (не двоичные). двукратный поворот?

12. Как производится балансировка дерева при удалении верхушки?

13. Как описывается структура верхушки дерева с дополнительными указателями на родителей?

14. Какие достоинства и недочеты имеют деревья с дополнительными указателями на родителей?

15. Зачем можно использовать деревья с дополнительными указателями на родителей?

16. В чем состоит основная сложность реализации не-двоичных деревьев?

17. Какие Деревья общего вида (не двоичные). списковые структуры можно использовать для реализации не-двоичных деревьев?

18. Какую структуру обязаны иметь верхушки не-двоичных деревьев при реализации их при помощи списков?

19. Как реализуется вывод вершин не-двоичного дерева, представленного при помощи списков?

20. Как реализуется добавление верхушки в не-двоичное дерево, представленное при помощи списков?

21. Как реализуется удаление Деревья общего вида (не двоичные). верхушки из не-двоичного дерева, представленного при помощи списков?

22. Какие есть разновидности графов?

23. Какие методы можно использовать для представления графов как структур данных?

24. Что такое матрица смежности и как она описывается?

25. Какие структуры данных нужны для реализации списков смежности?

26. Какие главные задачки появляются при использовании графов?

27. Как реализуются операции прибавления и удаления Деревья общего вида (не двоичные). ребер в графе?

28. Как реализуются операции прибавления и удаления вершин в графе?

29. Какие шаги содержит в себе метод поиска в глубину?

30. Какие шаги содержит в себе метод поиска в ширину?


desyat-zapovedej-zakona-bozhiya-ishod-202-17.html
desyataya-lekciya-perevod-g-v-barishnikovoj.html
desyatichnaya-sistema-schisleniya-istoriya.html