§16. Списки и деревья | Из чего состоит дерево (informatika_09_34_pol)

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


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



Содержание урока

Списки

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

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

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

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

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

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

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


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


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

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

Рис. 3.9

Рис. 3.9

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

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

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

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

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

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

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

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

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

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

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

Рис. 3.10

Рис. 3.10

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

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



Следующая страница Где используются деревья?



Cкачать материалы урока







Наверх