Уроки 25 - 26
§16. Списки и деревья
Содержание урока
Из чего состоит дерево?
Из чего состоит дерево?
Дерево состоит из узлов, связанных между собой. Самый первый узел, расположенный на верхнем уровне (в него не входит ни одна стрелка), — это корень дерева, от него отходят ветви дерева (рис. 3.9). Конечные узлы, из которых не выходит ни одна ветвь, называются листьями. Все остальные узлы, кроме корня и листьев, — это внутренние узлы.
Назовите корень, листья и внутренние узлы дерева, изображённого на рис. 3.9.
Рис. 3.9
Как вы думаете, можно ли считать список частным случаем дерева? Почему?
Путь — это последовательность узлов, где каждый следующий связан с предыдущим.
Можно ли считать, что путь — это список? Почему?
Высота дерева — это наибольшая длина пути от корня дерева к листу.
Определите высоту дерева на рис. 3.9.
Поддерево — это часть дерева, которая тоже представляет собой дерево.
Например, в дереве на рис. 3.9 узлы В, D и Е вместе с ветвями BD и BE составляют поддерево.
Назовите другие поддеревья дерева на рис. 3.9.
Из двух связанных узлов тот, который находится на более высоком уровне, называется родителем, а другой — сыном. Корень — это единственный узел, у которого нет родителя; у листьев нет сыновей.
Используются также понятия «предок» и «потомок». Потомок какого-то узла — это узел, в который можно перейти по стрелкам от узла-предка. Соответственно, предок какого-то узла — это узел, из которого можно перейти по стрелкам в данный узел.
Дерево часто используют для изображения родственных связей семьи: такое дерево называется генеалогическим деревом. В корне записывают самого дальнего известного предка, остальные узлы — это его потомки: на первом уровне — дети, на втором — внуки и т. д. (рис. 3.10).
Рис. 3.10
Для дерева на рис. 3.9 определите родителей, предков и потомков узлов Е, С и А.
Составьте в тетради генеалогическое дерево вашей семьи.
Следующая страница 
Где используются деревья?
Cкачать материалы урока
