АТД дерево

Дерево – совокупность элементов называемые узлами, один из которых определен как корень и отношения, образующих иерархическую структуру узлов. Заметим, что узлы могут быть любого типа по аналогии с элементами списка, а при реализации отличаются структурой узлов. Формально дерево можно определить (рекуррентно):

1. Один узел является деревом, этот же узел является корнем. Также выделяют пустое дерево, содержащее Λ(лямду).

2. Пусть n – узел, а T1, T2 и …Tk деревья с корнями n 1, n 2 … n k, тогда можно построить новое дерево, сделав узел n родителем узлов n 1, n 2 … n k и получим T1…Tk - поддеревьями, а n 1, n 2 … n k – корнями этих деревьев, кроме того они являются сыновьями узла n.

Путем из узла n 1 в узел n k является последовательность узлов n 1, n 2 … n k таких, что для всех ni узлов, образующих путь 2 ≤ i ≤ k, ni-1 является родителем узла ni.

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

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

- если, существует путь нулевой длины от узла до самого себя.

- если, существует путь из узла А в узел В, то узел А является предком узла В, а В потомком узла А.

Любой узел одновременно является и предком самого себя. Истинным предком или истинным потомком является предок (или потомок) не являющимся таковым самого себя.

Корень – это узел, не имеющий истинного предка. Узлы не имеющих истинных потомков называются листьями.

Под дерево, какого – либо дерева можно определить как узел со всеми его потомками. Высотой узла дерева называется длина самого длинного пути от этого узла до любого из его листьев – потомка. Высота дерева совпадает с высотой корня. Глубина узла – длина пути от корня до этого узла при этом путь истинен.