"Информатика", Рудченко Т.А., Семёнов А.Л. / Под ред. Семёнова А.Л.
Дерево бусин — схема с верхней корневой бусиной и связями, ведущими к нижним бусинам. Чтобы описывать положение каждой бусины, ей назначают уровень: корень имеет уровень 0, а каждый переход вниз увеличивает его на единицу. Уровень показывает длину пути от корня, помогает находить бусины на одинаковом расстоянии, сравнивать ветви и определять, насколько глубоко расположена часть дерева.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Дерево бусин — иерархическая схема, в которой бусины соединены связями от верхней бусины к нижним. Такая схема показывает, как один элемент может вести к нескольким следующим элементам. Она нужна, чтобы удобно описывать разветвлённые структуры.
Корневая бусина — самая верхняя бусина дерева, с которой начинается отсчёт уровней. У неё нет родительской бусины в пределах данного дерева. От корня мысленно движутся вниз, чтобы определить положение остальных бусин.
Уровень бусины — количество переходов по связям от корневой бусины до данной бусины. Корень имеет уровень 0, а бусина, до которой нужно сделать два перехода, находится на уровне 2. Это число показывает удалённость бусины от начала дерева.
Родительская и дочерняя бусины — две связанные бусины, между которыми верхняя является родительской, а нижняя — дочерней. У родителя может быть несколько дочерних бусин, но у каждой дочерней бусины в этом пути только один непосредственный родитель. Такая пара помогает переходить от одного уровня к следующему.
Корневую бусину выделяют потому, что дереву нужна точка, от которой можно однозначно начать описание. Если выбрать разные начала, расстояния до бусин могли бы считаться по-разному. Направление связей сверху вниз показывает, какие бусины являются предками, а какие — потомками, и делает строение дерева понятным.
Корневая бусина имеет уровень 0, потому что путь от неё до неё самой не содержит переходов. Когда мы идём к непосредственно соединённой бусине, появляется один переход, поэтому уровень становится 1. Каждый следующий шаг добавляет ровно одну связь, так что число уровня естественно увеличивается на единицу.
Уровень находят по единственному пути от корня к нужной бусине. Сначала выбирают корень, затем прослеживают ветвь и считают связи, а не сами бусины. Если путь содержит пять связей, бусина находится на уровне 5, даже если в других ветвях дерева элементов больше или меньше.
Одинаковая высота на рисунке не всегда означает одинаковый уровень, потому что рисунок может быть расположен не строго по горизонтальным рядам. Бусина визуально ниже другой иногда соединена с корнем более коротким или более длинным путём. Поэтому положение на листе служит подсказкой, но окончательный ответ даёт подсчёт связей.
Уровни позволяют описывать строение дерева без длинного перечисления всех связей. По ним можно найти все бусины на определённом расстоянии от корня, сравнить положение элементов на разных ветвях и определить глубину дерева. При этом уровень описывает путь к бусине, а не число её потомков.
В таблице сначала найдите нужную ситуацию, затем посмотрите, какое действие требуется выполнить. При подсчёте двигайтесь от корня к выбранной бусине и отмечайте каждую связь. Если нужно сравнить элементы, сравнивайте именно полученные числа уровней.
| Элемент или ситуация | Как определить уровень | Что важно помнить |
|---|---|---|
| Корневая бусина | Уровень равен 0 | Отсчёт начинается с корня |
| Бусина, соединённая непосредственно с корнем | Сосчитать одну связь от корня | Уровень равен 1 |
| Бусина на втором уровне | Найти путь из двух связей от корня | Не считать количество бусин вместо связей |
| Бусина на произвольном уровне | Посчитать все связи на пути от корня | Каждый переход учитывается один раз |
| Бусины одного уровня | Сравнить длины их путей от корня | Они могут быть на разных ветвях |
| Самый глубокий уровень дерева | Найти наибольший уровень среди всех бусин | Он соответствует максимальной длине пути |
Условие. По изображённому дереву нужно определить уровень каждой бусины, начиная с верхней. Известно только, что связи образуют обычное дерево с одним корнем. Требуется не пропустить ни одной связи на ветвях.
Ответ. Уровни получают последовательные значения 0, 1, 2, 3 и далее по длине пути. На одном уровне могут оказаться несколько бусин, если от корня до каждой из них ведёт одинаковое число связей. Важно подписывать уровень каждой бусины по её собственному пути.
Условие. Дана часть дерева: известны уровни нескольких бусин и связи между ними, но одна подпись пропущена. Нужно определить уровень пропущенной бусины и восстановить остальные подписи. Используем связь между родителем и дочерним элементом.
Ответ. Если родитель имеет уровень 4, его непосредственная дочерняя бусина имеет уровень 5. При двух переходах вниз от уровня 4 получаются уровни 5 и 6. Проверка должна привести к корню с уровнем 0.
Условие. В разветвлённом дереве нужно найти все бусины заданного уровня, определить самый глубокий уровень и сравнить две бусины на разных ветвях. Ветви могут иметь разную длину, поэтому нельзя считать их одинаковыми автоматически.
Ответ. Все бусины уровня 3 находятся на расстоянии трёх связей от корня. Если две бусины имеют уровни 2 и 5, первая расположена ближе к корню, а вторая глубже. Самый глубокий уровень равен максимальному числу, полученному при проверке всех ветвей.
Нумерация с 1 вместо 0. Так происходит, когда считают саму корневую бусину первым объектом, а не считают переходы. Проверьте себя вопросом: сколько связей нужно пройти от корня до корня?
Уровнем считают количество дочерних бусин. Эти величины описывают разные свойства: уровень связан с расстоянием до корня, а дочерние бусины — с ветвлением. Для проверки посчитайте связи на пути, не пересчитывая элементы ниже.
При подсчёте пропускают одну связь. Ошибка появляется, когда путь прослеживают слишком быстро или считают только промежуточные бусины. Проведите пальцем по каждой связи от корня и отметьте каждый переход.
Уровень определяют только по высоте на рисунке. Схема может быть нарисована неровно, поэтому визуальная позиция иногда вводит в заблуждение. Проверьте уровень по единственному пути от корня, а затем уже сравнивайте расположение на листе.
До изучения уровней нужно уметь читать схемы, находить связи и различать верхние и нижние элементы. Тема опирается на ветвление: у одной бусины может быть несколько дочерних бусин. Позже уровни помогут понимать деревья, иерархические структуры, файловые системы и алгоритмы обхода дерева.
Почему уровень корневой бусины равен 0, а не 1?
До корневой бусины от самой себя не нужно делать ни одного перехода. Поэтому длина пути от корня до корня равна 0, и именно этот номер получает корневая бусина.
Как определить уровень бусины, если дерево сильно разветвляется?
Найдите путь от корневой бусины до нужной и посчитайте все связи на этом пути. Разветвления в других частях дерева не влияют на результат.
Могут ли бусины на одной высоте рисунка иметь разные уровни?
Да, могут, если рисунок выполнен не по уровням. Уровень определяется количеством связей от корня, а не только тем, где бусина расположена на листе.
Чем уровень бусины отличается от количества её дочерних бусин?
Уровень показывает расстояние от корня по связям. Количество дочерних бусин показывает, сколько элементов находится непосредственно ниже данной бусины, поэтому это разные характеристики.
Как найти самый глубокий уровень дерева?
Нужно определить уровни всех бусин и выбрать наибольшее значение. Самый глубокий уровень принадлежит бусинам, до которых от корня нужно пройти больше всего связей.
Уровни бусин в дереве
