Лекция 5. Дерево – структура данных, позволяющая смоделировать иерархические отношения

Деревья

Дерево – структура данных, позволяющая смоделировать иерархические отношения. У каждого элемента этой структуры имеется свой единственный «непосредственный начальник» и некоторое количество «подчиненных». Примерами древовидной структуры могут служить подчиненность служащих в армии, структура бюрократического управления производством, почтовый адрес, организация хранения данных в файловой подсистеме системы Windows, и другие.

Термины: корень, узлы, листы, ветки, поддерево, пень, предок, потомок, братья, уровень, высота.

Определение (рекурсивное):

D_n – n-арное дерево (n>=2), D_n^o – непустое n-арное дерево.

D_n = (либо пусто, либо D_n^o);

D_n^o = (i:инф; n штук D_n)

n=2 - бинарное дерево.