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


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


Графом называется совокупность объектов, называемых вершинами графа, и связей между ними, которые принято называть дугами графа. Граф, в котором каждая связь имеет направление, называется направленным графом. Принято изображать вершины графа точками на плоскости, а связи между ними - отрезками (направленные связи - стрелками). Путем на графе называется последовательность вершин, соединенных дугами. Для направленного графа направление пути должно совпадать с направлением каждой дуги пути.

Пара вершин направленного графа, соединенная стрелкой, называется главной и подчиненной вершиной (или хозяином и слугой, или отцом и сыном). Вершина может быть одновременно отцом и сыном. Циклом в направленном графе называется замкнутый путь, то есть путь, начало и конец которого совпадают. Если граф не имеет циклов, то обязательно имеется хотя бы одна вершина, в которую не входит ни одна стрелка. Такая вершина называется корневой. Граф, у которого ровно одна корневая вершина, является связным. В таком графе для каждой вершины существует путь из корневой вершины в данную. Наконец, деревом называется связный направленный граф без циклов, у каждой вершины которого не более одного хозяина. На самом деле в дереве все вершины, кроме корня, имеют хозяина. В каждую вершину дерева из корня ведет ровно один путь, то есть существует взаимно-однозначное соответствие между вершинами и путями. Если вершина не имеет подчиненных вершин, то она называется концевой вершиной или тупиком или листом.

Назовем корневую вершину вершиной первого уровня, ее сыновей - вершинами второго уровня, сыновей ее сыновей - вершинами третьего уровня и т.д. Максимальный уровень называется глубиной дерева. Далее, для каждой вершины перенумеруем дуги, выходящие из этой вершины. Можно ввести так называемый лексикографический порядок на множестве вершин дерева. Именно, для каждой пары вершин возьмем два пути, ведущие из корня в эти вершины. Тогда эти пути либо один продолжает другой, либо они расходятся с некоторой точки.


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



Книжный магазин