Дерево

Материал из WEGA
Версия от 13:35, 3 февраля 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Дерево(Tree) — связный граф без циклов. Чаще всего этот термин используется как краткая форма термина корневое дерево, т.е. конечное множество одной или нескольких вершин таких, что, во-первых, среди них существует только одна особая вершина, называемая корнем, и, во-вторых, остальные вершины делятся на [math]\displaystyle{ d }[/math] непересекающихся множеств [math]\displaystyle{ T_{1}, \, T_{2}, \ldots, \, T_{d} }[/math] каждое из которых само является деревом. Множества [math]\displaystyle{ T_{1}, \, T_{2}, \ldots, \, T_{d} }[/math]называются поддеревьями корня. Если порядок в этих деревьях существен, дерево называется упорядоченным деревом, в противном случае оно иногда называется неупорядоченным деревом. Дерево может быть представлено как граф, в котором корневая вершина представлена вершиной, соединенной дугами с вершинами, представляющими корни каждого из ее поддеревьев. Таким образом, в терминах теории графов можно дать другое определение (ориентированного) дерева: дерево — это ориентированный бесконтурный граф такой, что, во-первых, существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем), во-вторых, в каждую из оставшихся вершин входит ровно одна дуга, и, в-третьих, существует единственный путь из корня в любую другую вершину.

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

Tree.png

См. также

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.