Организация и функционирование компьютеров


Использование указателей для обработки деревьев - часть 2


В первом случае будем предполагать, что более длинный путь следует за более коротким. Во втором случае порядок определяется номерами первых несовпадающих дуг путей.

Приведем пример дерева. В каждой вершине изобразим три цифры: уровень вершины дерева, номер в списке слуг хозяина данной вершины и общий номер в множестве вершин дерева.

                                                                               1.1.1


                     2.1.2                             2.2.8                                  2.3.10                           2.4.11

 


        3.1.3                      3.2.6                   3.1.9                  3.1.12                    3.2.13                 3.3.18

 


     4.1.4                4.2.5             4.1.7                  4.1.14                 4.2.15                 4.3.16              4.4.17

Тупиками являются вершины с номерами 4,5,7,9,10, 12,14,15,16,17,18.

Важным свойством дерева является свойство подобия, которое заключается в том, что множество всех потомков данного хозяина (сыновей, сыновей сыновей и т.д.) образуют дерево. Оно является поддеревом дерева с корнем в данной вершине. Такое поддерево иногда называют ветвью дерева. В частности, каждое дерево состоит из корня дерева и нескольких ветвей, корнями которых служат все вершины первого уровня дерева.

Деревом изображаются любые иерархические структуры, которые очень часто встречаются на практике. Например структура подразделений компании или структура административного деления регионов. Деревом является классификация видов животных или перечень номенклатуры изделий (и вообще, любая классификация). Иерархия объектов в реальной действительности приводит к иерархии описаний объектов в памяти компьютера.

Как и в случае списков, описание вершины дерева состоит из двух частей: содержательной информации (описания объекта) и структурной информации (положения объекта в дереве). В данный момент нас интересует структурная информация.


- Начало -  - Назад -  - Вперед -