Дерево (структура данных)

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск
Простой пример ориентированного дерева

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

Самую верхний, начальный узел дерева обычно называют "корнем". Самые нижние, конечные узлы - "листьями". У неориентированного дерева корнем можно объявить любую любой узел, листьями будут те, у которых одна единственная связь. У правильного ориентированного дерева - такого, что к каждому узлу идёт не более одной связи, корнем будет единственная вершина, к которой не идёт ни одной связи, а листьями - те, из которых ни одной связи не выходит.