Можно ли сказать что список это частный случай двоичного дерева почему

Учитель информатики

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

Списки и деревья.

Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)

§16. Списки и деревья.

Списки

Ключевые слова:

Список — это последовательность элементов, в которой важен порядок их расположения. Говорят, что список — это упорядоченная последовательность.

Как можно назвать неупорядоченную последовательность, в которой элементы не повторяются?

Для каждого элемента в списке, кроме первого, можно назвать предыдущий элемент; для каждого элемента, кроме последнего, — следующий (рис. 3.7).

Рис. 3.7

Для списка на рис. 3.7 назовите:

а) первый и последний элементы;
б) предыдущий элемент для «И»;
в) предыдущий элемент для «П»;
г) следующий элемент для «Г»;
д) следующий элемент для «Т».

Списки могут служить моделями для каких-то объектов. Например, список на рис. 3.7 — это модель слова «полиглот». Предложение можно представить в виде списка слов, абзац — в виде списка предложений, текст — в виде списка абзацев.

Используя дополнительные источники, выясните, от какого иностранного слова произошло слово «полиглот» и что оно обозначает.

Структура данных «список» есть во многих языках программирования. Списки обычно записывают в квадратных скобках, перечисляя через запятую их элементы по порядку, с первого до последнего. Например, так:

[’Amicus’, ’Socrates’, ’sed’, ’magis’, ’arnica’, ’veritas’]

Используя дополнительные источники, выясните значение известной фразы, которую задаёт этот список слов.

Используя дополнительные источники, выясните, название какого языка программирования образовано от слов «обработка списков».

В список можно добавлять новые элементы (до или после заданного элемента), можно также заменять и удалять элементы. Если применять эти операции к словам (спискам букв), то мы можем из одного слова получить другое. Например, слово КОРОНА можно получить из слова КРАН так:

Назовите операции, которые были выполнены на каждом шаге.

Но это не единственный вариант такого преобразования.

Постарайтесь найти самый короткий вариант получения слова КОРОНА из слова КРАН.

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

Таблица 3.7

Как можно преобразовать слово СКАНЕР в слово ПРИНТЕР? Определите «стоимость» такого преобразования — «расстояние» между словами.

Подобная задача возникает при исследовании белков человека и животных, этим занимается наука биоинформатика. Белки — это цепочки аминокислот, каждая аминокислота обозначается латинской буквой. Срав нить два белка — это значит определить, как проще всего из одного белка получить другой.

Что такое дерево?

Предположим, в некоторой фирме есть директор, ему подчиняются главный инженер и главный бухгалтер, у каждого из них есть свои подчинённые. Если мы захотим нарисовать схему управления этой фирмы, она получится многоуровневой (рис. 3.8).

Рис. 3.8

Такая структура, в которой одни элементы «подчиняются» другим, называется иерархической. В информатике её называют деревом.

Дело в том, что, если перевернуть эту схему вверх нотами, она становится похожа на дерево.

Дерево — это структура данных, которая служит моделью многоуровневой структуры (иерархии).

Несколько деревьев образуют лес.

Используя дополнительные источники, выясните, от какого иностранного слова произошло слово «иерархия».

Из чего состоит дерево?

Дерево состоит из узлов, связанных между собой. Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка), — это корень дерева, от него отходят ветви дерева (рис. 3.9). Конечные узлы, из которых не выходит ни одна ветвь, называются листьями. Все остальные узлы, кроме корня и листьев, — это внутренние узлы.

Назовите корень, листья и внутренние узлы дерева, изображённого на рис. 3.9.

Рис. 3.9

Как вы думаете, можно ли считать список частным случаем дерева? Почему?

Путь — это последовательность узлов, где каждый следующий связан с предыдущим.

Можно ли считать, что путь — это список? Почему?

Высота дерева — это наибольшая длина пути от корня дерева к листу.

Определите высоту дерева на рис. 3.9.

Поддерево — это часть дерева, которая тоже представляет собой дерево.

Например, в дереве на рис. 3.9 узлы В, D и Е вместе с ветвями BD и BE составляют поддерево.

Назовите другие поддеревья дерева на рис. 3.9.

Из двух связанных узлов тот, который находится на более высоком уровне, называется родителем, а другой — сыном. Корень — это единственный узел, у которого нет родителя; у листьев нет сыновей.

Используются также понятия «предок» и «потомок». Потомок какого-то узла — это узел, в который можно перейти по стрелкам от узла-предка. Соответственно, предок какого-то узла — это узел, из которого можно перейти по стрелкам в данный узел.

Дерево часто используют для изображения родственных связей семьи: такое дерево называется генеалогическим деревом. В корне записывают самого дальнего известного предка, остальные узлы — это его потомки: на первом уровне — дети, на втором — внуки и т. д. (рис. 3.10).

Рис. 3.10

Для дерева на рис. 3.9 определите родителей, предков и потомков узлов Е, С и А.

Составьте в тетради генеалогическое дерево вашей семьи.

Где используются деревья?

Типичный пример иерархии — различные классификации (животных, растений, минералов, химических соединений). Например, отряд Хищные делится на два подотряда: Псообразные и Кошкообразные. В каждом из них выделяют несколько семейств (рис. 3.11).

Рис. 3.11

Конечно, на этой схеме показаны не все семейства, остальные обозначены многоточием.

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

Глава 1. Псообразные

Глава 2. Кошкоообразные

1) В некоторых файловых системах файл может «принадлежать» нескольким папкам одновременно. При этом древовидная структура, строго говоря, нарушается.

Рис. 3.12

Запишите по схеме на рис. 3.12 полный адрес файла Расходы.odt. Если вы работаете в операционной системе Windows, считайте, что папка Документы находится в корневой папке диска С:, для системы Linux — в папке /home/sonya.

Алгоритм вычисления арифметического выражения может быть представлен в виде модели-дерева (рис. 3.13).

Рис. 3.13

Здесь листья — это числа и переменные, а корень и промежуточные узлы — знаки операций. Вычисления выполняются «снизу вверх» — от листьев — к корню.

Представление арифметического выражения в виде дерева позволяет выделить независимые друга от друга операции, которые современные процессоры могут выполнять одновременно (или, как говорят, параллельно). Например, на рис. 3.14 видно, что умножение b • с никак не зависит от сложения a + 3. Если считать, что время выполнения всех операций одинаково и равно T, то процессор, имеющий несколько устройств для выполнения арифметических операций, вычислит это выражение за время 3Т вместо 5Т.

В дереве для вычисления арифметического выражения (см. рис. 3.13) каждый узел может иметь не более двух сыновей, поэтому оно называется двоичным (или бинарным). От расположения сыновей зависит результат вычитания и деления, поэтому используют термины «левый сын» и «правый сын», «левое поддерево» и «правое поддерево».

Используя дополнительные источники, выясните, от какого иностранного слова произошло слово «бинарный».

Постройте дерево, соответствующее арифметическому выражению (5*b+а)/(2*а+3*b+6).

Перебор вариантов

С помощью дерева можно изобразить многошаговый процесс, в котором на каждом шаге делается выбор из нескольких вариантов. Например, русские богатыри в сказках часто выбирали на развилке, куда поехать — налево, прямо или направо. В игре «крестики-нолики» каждый игрок на каждом ходу тоже выбирает один из всех возможных вариантов.

Например, построим все двухбуквенные слова, которые можно записать с помощью алфавита <А, Б, В>. Начнём с пустого слова, в котором нет ни одной буквы (на рис. 3.14 оно изображено чёрным кружком в корне дерева), и будем на каждом шаге добавлять в конец слова одну из трёх возможных букв (см. рис. 3.14).

Рис. 3.14

Чтобы найти само слово, нужно выписать метки всех узлов на пути от корня до листа. Например, узлы, выделенные серым фоном на рис. 3.14, соответствуют слову БВ.

Можно рисовать это дерево иначе, повернув его на бок. В § 15 такая запись использовалась при выборе оптимального маршрута.

Разведчик выяснил, что ключ к замку от сейфа состоит из трёх символов, причём могут использоваться буквы из алфавита <А, В, С, D>. Две одинаковые буквы не могут стоять рядом. Рядом с буквой D обязательно должна стоять буква А. Если в ключе есть буква В, то там не может быть буквы С. Постройте дерево перебора вариантов и подсчитайте, сколько различных ключей удовлетворяют этим условиям.

Дерево для двоичного кода

Для двоичного кода тоже можно построить дерево.

Например, для кода дерево выглядит так (рис. 3.15).

Рис. 3.15

Из каждого узла выходят две ветви — при движении по левой ветви мы выбираем 0, при движении по правой — 1. В некоторых узлах записаны буквы, остальные обозначены точками. Участки ветвей, соединяющие два узла, называются рёбрами. Чтобы получить код буквы, нужно пройти по ветвям от корня к узлу, в котором записана эта буква, и выписать коды всех пройденных рёбер.

Проверьте, выполняется ли для этого кода условие Фано: ни одно из кодовых слов не совпадёт с началом другого кодового слова.

Как сразу определить это по дереву? Где должны располагаться узлы с буквами, чтобы условие Фано выполнялось?

Постройте дерево для следующего кода:

Выполняется ли для него условие Фано? Сколько букв можно добавить в кодовую таблицу, чтобы все коды были не длиннее трёх символов и выполнялось условие Фано?

Выводы
Интеллект-карта

Выводы
• Список — это упорядоченная последовательность элементов. Для каждого элемента в списке, кроме первого, можно назвать предыдущий элемент; для каждого элемента, кроме последнего, — следующий.
• В список можно добавлять новые элементы (до или после заданного элемента), можно также заменять и удалять элементы.
• Дерево — это структура данных, которая служит моделью многоуровневой структуры (иерархии). Несколько деревьев образуют лес.
• Дерево состоит из узлов, связанных между собой. Самый первый узел, расположенный на верхнем уровне, — это корень дерева. От корня отходят ветви дерева. Участок ветви, соединяющий два узла, называется ребром. Конечные узлы, из которых не выходит ни одна ветвь, называются листьями.
• Путь — это последовательность узлов, где каждый следующий связан с предыдущим.
• Высота дерева — это наибольшая длина пути от корня дерева к листу.
• Поддерево — это часть дерева, которая тоже представляет собой дерево.
• Деревья можно использовать для описания классификации, иерархической файловой системы, записи арифметических выражений, перебора вариантов, анализа и построения кодов.

Рис. 3.16

Вопросы и задания

1. Чем отличается список от множества?
2. Можно ли сказать, что список — это частный случай двоичного дерева? Почему?
3. Может ли количество листьев дерева совпадать с количеством его узлов?
4. Сколько узлов может быть в двоичном дереве высотой 2? Высотой 3? Для каждого случая назовите наибольшее и наименьшее количество узлов.
5. Сколько рёбер может быть в двоичном дереве высотой 2? Высотой 3? Для каждого случая назовите наибольшее и наименьшее количество рёбер.
6. Может ли двоичное дерево высоты 3 содержать больше узлов, чем дерево высоты 5?
7. Если для кода выполняется обратное условие Фано (ни одно кодовое слово не совпадает с окончанием другого кодового слова), то сообщение можно декодировать однозначно. Какое дерево нужно построить, чтобы убедиться в выполнении обратного условия Фано?
8. Выполните по указанию учителя задания в рабочей тетради.

Источник