Лабораторная работа № 12. Бинарные деревья
Дерево — это граф, который характеризуется следующими свойствами: существует единственный элемент (узел или вершина), на который не ссылается никакой другой и который называется корнем; начиная с корня и следуя по определенной цепочке указателей, можно осуществить доступ к любому элементу структуры; на каждый элемент, кроме корня, имеется единственная ссылка. Бинарное дерево – это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев: в левом поддереве содержатся ключи, имеющие значения, меньшие, чем значение данного узла, в правом поддереве содержатся ключи, имеющие значения, большие, чем значение данного узла.
4. Разработать программу работы с бинарным деревом, в которую включить основные функции манипуляции данными и функцию в соответствии со своим вариантом из таблицы, представленной ниже.
Теоретические сведения: Нелинейные связные структуры
Односвязный список всегда линейный. Двусвязный список может и не быть линейным, если второй указатель каждого элемента списка задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому первым указателем элемента. В еще более общем случае каждый элемент связного списка может содержать произвольное конечное число связок, одинаковое или разное в различных элементах. В результате такого обобщения получается многосвязный список, каждый элемент которого входит одновременно во столько разных односвязных списков, сколько имеется связок в соответствующем элементе. При этом не обязательно чтобы каждый элемент непременно входил во все односвязные списки. Такой многосвязный список как бы прошит в разных направлениях многими связками. Поэтому многосвязные списки иногда называют прошитыми списками. Используется также еще одно название многосвязных списков — плексы.
Наиболее общий вид многосвязной структуры — многосвязная структура, которая характеризуется следующими свойствами:
1. Каждый элемент структуры содержит произвольное число направленных связок с другими элементами (или ссылок на другие элементы).
2. С каждым элементом может связываться произвольное число других элементов (т.е. каждый элемент может быть объектом ссылки произвольного числа других элементов).
3. Каждая связка в структуре имеет не только направление, но и вес.
Такую многосвязную структуру называют сетевой структурой или сетью. Логически сеть эквивалентна взвешенному ориентированному графу общего вида, и поэтому вместо термина “сеть” часто употребляется термин ”графовая структура” или просто “граф”, а вместо термина “элемент” термин “узел”.
Сетевые структуры широко применяются при организации банков данных, систем управления базами данных, в системах программ имитационного моделирования сложных комплексов и т.д.
Сетевые структуры — весьма общий и гибкий класс связных списков. Рассмотрим частные случаи многосвязных списков — древовидные структуры или просто деревья.
Деревом называется сетевая структура, которая характеризуется следующими свойствами:
1. Существует единственный элемент, или узел, на который не ссылается никакой другой элемент и который называется корнем.
2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры.
3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.
Определенная таким образом структура называется также корневым деревом. Название “дерево” проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется ветвью. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются листьями. Узел, ни являющийся листом или корнем, считается промежуточным, или узлом ветвления. Если в дереве узел X ссылается на узел Y, то X называется ”родителем”, а Y — его “сыном ”. Все узлы с общим родителем являются “братьями”. Число сыновей у родителя X — степень исхода узла X. При графическом представлении дерева упорядоченность сыновей любого родителя обычно задается изображением узлов — сыновей в порядке убывания их старшинства слева направо.
Если число сыновей у каждого родителя не больше m — для каждого узла, то соответствующее дерево называется m-арным деревом. Если степень исхода равна m или нулю для каждого узла, то дерево называется полным m-арным деревом. Обычно дерево представляется в машинной памяти в форме многосвязного списка, в котором каждый указатель соответствует дуге. Это представление называется естественным представлением дерева. В одной из наиболее общих разновидностей представления каждому узлу дерева ставится в соответствие элемент многосвязного списка, причем в каждом элементе отводятся поля: поле данных, поле степени исхода, поле указателей, число которых равно степени исхода.
Частный случай дерева — бинарное дерево. Бинарным деревом называется дерево с m = 2. любое m-арное дерево может быть преобразовано в эквивалентное ему бинарное дерево, которое проще исходного с точки зрения изучения, представления в памяти и обработке. Для этого сначала в каждом узле исходного дерева вычеркиваем все ветви, кроме самой левой, которая соответствует ссылке на старшего сына, после этого соединяем горизонтальными ветвями те узлы одного уровня, которые братьями в исходном дереве.
Важнейшие операции над бинарными деревьями: добавление и исключение некоторого поддерева, обход узлов. Обход осуществляется: обходом сверху (шаги выполняются в порядке 1, 2, 3), обход слева направо (2, 1, 3) и обход снизу (2, 3, 1). Можно существенно ускорить операцию обхода, используя прошивки. Это позволит обойтись без стека, требуемого при обходе непрошитого дерева. Вместо пустых указателей можно поместить вспомогательные связки, которые называются прошивками.
В отличие от основных структурных связок, каждая прошивка адресует предшествующий или последующий узел дерева в выбранной схеме обхода.
Если прошивка находится в поле левого указателя, то она адресует предыдущий узел дерева, а прошивка в поле правого указателя адресует следующий узел в выбранной схеме обхода.
При исключении элемента проблема возврата элементов многосвязной списковой структуры в свободный список может решаться разными методами. Наиболее известны: метод счетчика (после каждый операции исключения элемента делается проверка, остался ли этот элемент хотя бы в каком-нибудь одном функциональном списке, и в случае отрицательного ответа элемент присоединяется к свободному списку), метод сборки мусора (освободившийся элемент как бы “повисает ”до тех пор, пока не будет исчерпан свободный список. После этого запускается процедура сборки мусора, которая отыскивает все освободившиеся к этому времени элементы и включает их в свободный список).
7 Древовидные структуры данных
В задачах различного рода данные могут быть связаны между собой, не только образуя линейную последовательность (по горизонтали), но и иерархически (по вертикали, т.е. находиться на разных уровнях). Отношения типа предок-потомок являются иерархическими, тогда как брат-сестра — на одном уровне. Или такая иерархия:
Деревом называется структура, которая характеризуется следующими свойствами:
существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем.
каждый элемент связан с несколькими элементами следующего уровня иерархии. Эти элементы могут быть в свою очередь деревьями (поддеревьями).
3)каждый элемент промежуточного уровня порожден только одним элементом более высокого уровня. Элементы дерева, которые не ссылаются на другие элементы, являются терминальными (т.е. конечными)
или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами.
Таким образом дерево отражает иерархически упорядоченную структуру данных, в которой прослеживаются связи между элементами предыдущего (верхнего) уровня или предками и элементами следующего уровня — потомками.
Можно считать список деревом, у которого каждый узел имеет не более одного «поддерева». Поэтому список называется также «вырожденным деревом».
Существует несколько способов изображения древовидной структуры. Например, пусть базовый тип Т есть множество букв. Древовидную структуру, образованную с какой-либо целью на таком типе можно изобра-
а) вложенными множествами (рис. 17);
Графом дерево представляется нагляднее, но вверх ногами (корнем).
Узлы располагаются по уровням. Корень – нулевой уровень и т.д. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.
Число непосредственных потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева. Наше дерево – дерево третьей степени.
Число ветвей или ребер, которые нужно пройти, чтобы продвинуться от корня к узлу х, называется длиной пути к х. Корень имеет длину пути 0, его непосредственные потомки – длину пути 1 и т.д. Вообще узел на уровне i имеет длину пути i.
Длина пути дерева – это сумма длин путей всех его узлов. Она также называется длиной внутреннего пути. Для нашего дерева длина пути равна 36. Средняя длина пути
i = \
где ni – число узлов на уровне i; n – число элементов.
Дерево, у которого ветви каждого узла упорядочены, называется упорядоченным деревом:
разные упорядоченные деревья
Особо важную роль играют упорядоченные деревья второй степени. Они называются бинарными деревьями или двоичными. Бинарное дерево – это конечное множество элементов (узлов), каждый из которых либо пуст (не связан с нижним уровнем, не имеет потомков, т.е. лист), либо является корнем (или узлом) с двумя различными бинарными поддеревьями – левым и правым.
Деревья, имеющие степень больше двух, называются сильно ветвящимися деревьями.
Пример бинарного дерева – Арифметическое выражение с двуместными операциями, где каждая операция – это ветвящийся узел с операндами в качестве поддеревьев, например выражение (a + b / c) * (d — e * f), представится в виде двоичного дерева следующим образом
В принципе, любое n–арное дерево может быть преобразовано в эквивалентное ему бинарное дерево.
Элемент дерева на который не ссылаются другие называется
Сообщить о нарушение
Ваше сообщение отправлено, мы постараемся разобраться в ближайшее время.
Поделиться тестом:
Попробуйте пройти эти тесты:
Простейший тест на IQ из нескольких вопросов
Какое имя подходит вам по знаку зодиака
Если вы родом из СССР, то точно сможете закончить фразы тех времен на все 10 из 10
Тест на интеллект: Если наберете 9/9, то уровень вашего IQ точно выше среднего
Главный тест на общие знания: насколько ты умён?
Тест по советским фильмам: Кто из актеров сказал эти известные всем слова?
Догадливы и эрудированны ли вы настолько, чтобы парировать 15 вопросов обо всём?
Ваш словарный запас на высоком уровне, если наберете в нашем тесте хотя бы 8/11 — ТЕСТ
Умеете ли вы готовить? Сложный кулинарный Блиц-тест ресторатора Ивана Шишкина
Тест, который покажет, каким животным вы являетесь в душе.
Что вас ждет в старости?
Если вы наберете 11/12 в этом тесте на эрудицию, то такого начитанного и разностороннего человека еще поискать
Не заглядывая в Гугл, сможете ответить хотя бы на половину вопросов этого теста?
Насколько Ваш мозг пошлый?
А вы сможете продолжить эти 13 крылатых фраз?
Cколько лет вашей душе?
Если вы знаете, где находятся эти города, то ваши знания географии достойны аплодисментов!
Сможете ли вы набрать 10/10 баллов в нашем тесте на общие знания?
Вы невероятно умны, если смогли пройти этот тест на 10 из 10
Если в этом тесте вы наберете 13/13, то вам пора поступать в Гарвард
Популярные тесты
Простейший тест на IQ из нескольких вопросов
Какое имя подходит вам по знаку зодиака
Если вы родом из СССР, то точно сможете закончить фразы тех времен на все 10 из 10
Тест на интеллект: Если наберете 9/9, то уровень вашего IQ точно выше среднего
Главный тест на общие знания: насколько ты умён?
Тест по советским фильмам: Кто из актеров сказал эти известные всем слова?
Догадливы и эрудированны ли вы настолько, чтобы парировать 15 вопросов обо всём?
Ваш словарный запас на высоком уровне, если наберете в нашем тесте хотя бы 8/11 — ТЕСТ
Умеете ли вы готовить? Сложный кулинарный Блиц-тест ресторатора Ивана Шишкина
Тест, который покажет, каким животным вы являетесь в душе.
Что вас ждет в старости?
Если вы наберете 11/12 в этом тесте на эрудицию, то такого начитанного и разностороннего человека еще поискать
Не заглядывая в Гугл, сможете ответить хотя бы на половину вопросов этого теста?
Насколько Ваш мозг пошлый?
А вы сможете продолжить эти 13 крылатых фраз?
Cколько лет вашей душе?
Если вы знаете, где находятся эти города, то ваши знания географии достойны аплодисментов!
Сможете ли вы набрать 10/10 баллов в нашем тесте на общие знания?
Вы невероятно умны, если смогли пройти этот тест на 10 из 10
Если в этом тесте вы наберете 13/13, то вам пора поступать в Гарвард
Преимущества
Можете встраивать тесты на Ваш сайт. Тест показывается нашем и других сайтах. Гибкие настройки результатов. Возможность поделиться тестом и результатами. Лавинообразный («вирусный») трафик на тест. Русскоязычная аудитория. Без рекламы!
Создавайте тесты онлайн, всё бесплатно. У нас можно бесплатно: создать тест онлайн для для учеников, друзей, сотрудников, для вашего сайта, с ответами и результатами — Все Бесплатно!
Пользователям
Вам захотелось отдохнуть? Или просто приятно провести время? Выбирайте и проходите онлайн-тесты, делитесь результатом с друзьями. Проверьте, смогут они пройти также как Вы, или может лучше?
Конструктор Тестов ру — это огромное количество интересных и бесплатных тестов на сообразительность, IQ, зрение, знания правил дорожного движения, программирования и многое другое. Если Вам понравилось, обязательно поделитесь со своими друзьями в социальных сетях или просто ссылкой. А еще Вы можете легко создать свой тест и его будут проходить десятки тысяч людей.
Внимание! Наши тесты не претендуют на достоверность – не стоит относиться к ним слишком серьезно!