Урок №11. Дерево. Перебор вариантов с помощью дерева.
Предположим, в некоторой фирме есть директор, ему подчиняются главный инженер и главный бухгалтер, у каждого из них есть свои подчинённые. Если мы захотим нарисовать схему управления этой фирмы, она получится многоуровневой (рис. 3.8).
Такая структура, в которой одни элементы «подчиняются» другим, называется иерархической. В информатике её называют деревом. Дело в том, что, если перевернуть эту схему вверх ногами, она становится похожа на дерево.
Дерево — это структура данных, которая служит моделью многоуровневой структуры (иерархии).
Несколько деревьев образуют лес.
Дерево состоит из узлов, связанных между собой. Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка), — это корень дерева, от него отходят ветви дерева (рис. 3.9). Конечные узлы, из которых не выходит ни одна ветвь, называются листьями. Все остальные узлы, кроме корня и листьев, — это внутренние узлы.
Назовите корень, листья и внутренние узлы дерева, изображённого на рис. 3.9.
Как вы думаете, можно ли считать список частным случаем дерева? Почему?
Путь — это последовательность узлов, где каждый следующий связан с предыдущим.
Можно ли считать, что путь — это список? Почему?
Высота дерева — это наибольшая длина пути от корня дерева к листу.
Определите высоту дерева на рис. 3.9.
Поддерево — это часть дерева, которая тоже представляет собой дерево.
Например, в дереве на рис. 3.9 узлы В, D и Е вместе с ветвями BD и BE составляют поддерево.
Назовите другие поддеревья дерева на рис. 3.9.
Из двух связанных узлов тот, который находится на более высоком уровне, называется родителем, а другой — сыном. Корень — это единственный узел, у которого нет родителя; у листьев нет сыновей.
Используются также понятия «предок» и «потомок». Потомок какого-то узла — это узел, в который можно перейти по стрелкам от узла-предка. Соответственно, предок какого-то узла — это узел, из которого можно перейти по стрелкам в данный узел.
Дерево часто используют для изображения родственных связей семьи: такое дерево называется генеалогическим деревом. В корне записывают самого дальнего известного предка, остальные узлы — это его потомки: на первом уровне — дети, на втором — внуки и т. д. (рис. 3.10).
Для дерева на рис. 3.9 определите родителей, предков и потомков узлов Е, С и А.
Типичный пример иерархии — различные классификации (животных, растений, минералов, химических соединений). Например, отряд Хищные делится на два подотряда: Псообразные и Кошкообразные. В каждом из них выделяют несколько семейств (рис. 3.11).
Конечно, на этой схеме показаны не все семейства, остальные обозначены многоточием.
В текстах иерархию часто представляют в виде многоуровневого списка. Например, оглавление книги о хищниках может выглядеть так:
Глава 1.
Псообразные
Псовые
Енотовые
Медвежьи
Глава 2. Кошкоообразные
2.1 Кошачьи
2.2 Гиеновые
2.3 Мангустовые
Работая с файлами и папками, мы тоже встречаемся с иерархией: классическая файловая система имеет древовидную структуру1*. Вход в папку — это переход на следующий (более низкий) уровень иерархии (рис. 3.12).
Запишите по схеме на рис. 3.12 полный адрес файла Расходы.odt. Если вы работаете в операционной системе Windows, считайте, что папка Документы находится в корневой папке диска С:, для системы Linux — в папке /home/sonya.
Алгоритм вычисления арифметического выражения может быть представлен в виде мод ел и-дерева (рис. 3.13).
Здесь листья — это числа и переменные, а корень и промежуточные узлы — знаки операций. Вычисления выполняются «снизу вверх» — от листьев — к корню.
В дереве для вычисления арифметического выражения (см. рис. 3.13) каждый узел может иметь не более двух сыновей, поэтому оно называется двоичным (или бинарным). От расположения сыновей зависит результат вычитания и деления, поэтому используют термины «левый сын» и «правый сын», «левое поддерево» и «правое поддерево».
Используя дополнительные источники, выясните, от какого иностранного слова произошло слово «бинарный».
Постройте дерево, соответствующее арифметическому выражению (5*b+a)/(2*a+3*b+6).
С помощью дерева можно изобразить многошаговый процесс, в котором на каждом шаге делается выбор из нескольких вариантов. Например, русские богатыри в сказках часто выбирали на развилке, куда поехать — налево, прямо или направо. В игре «крестики-нолики» каждый игрок на каждом ходу тоже выбирает один из всех возможных вариантов.
Например, построим все двухбуквенные слова, которые можно записать с помощью алфавита {А, Б, В}. Начнём с пустого слова, в котором нет ни одной буквы (на рис. 3.14 оно изображено чёрным кружком в корне дерева), и будем на каждом шаге добавлять в конец слова одну из трёх возможных букв (см. рис. 3.14).
Чтобы найти само слово, нужно выписать метки всех узлов на пути от корня до листа. Например, узлы, выделенные серым фоном на рис. 3.14, соответствуют слову БВ.
Можно рисовать это дерево иначе, повернув его на бок. В § 15 такая запись использовалась при выборе оптимального маршрута.
Разведчик выяснил, что ключ к замку от сейфа состоит из трёх символов, причём могут использоваться буквы из алфавита {А, В, С, D}. Две одинаковые буквы не могут стоять рядом. Рядом с буквой D обязательно должна стоять буква А. Если в ключе есть буква В, то там не может быть буквы С. Постройте дерево перебора вариантов и подсчитайте, сколько различных ключей удовлетворяют этим условиям.
Для двоичного кода тоже можно построить дерево. Например, для кода
Из каждого узла выходят две ветви — при движении по левой ветви мы выбираем 0, при движении по правой — 1. В некоторых узлах записаны буквы, остальные обозначены точками. Участки ветвей, соединяющие два узла, называются рёбрами. Чтобы получить код буквы, нужно пройти по ветвям от корня к узлу, в котором записана эта буква, и выписать коды всех пройденных рёбер.
Проверьте, выполняется ли для этого кода условие Фано: ни одно из кодовых слов не совпадёт с началом другого кодового слова. Как сразу определить это по дереву? Где должны располагаться узлы с буквами, чтобы условие Фано выполнялось?
Постройте дерево для следующего кода:
Выполняется ли для него условие Фано? Сколько букв можно добавить в кодовую таблицу, чтобы все коды были не длиннее трёх символов и выполнялось условие Фано?