Реализация дека
Дек – двунаправленный список, т.е.
type
tuzel = record
info: ..;
next,prev:pUzel;
end;
Var left,right: pUzel;
Поле next - слева направо, поле prev - справа налево, поэтому имеется две головы. Добавление и удаление аналогично за исключением того, что необходимо корректировать значение как у узла справа, так и слева.
Не линейная структура данных атд дерево
Дерево – совокупность элементов называемые узлами, один из которых определен как корень и отношения, образующих иерархическую структуру узлов. Заметим, что узлы могут быть любого типа по аналогии с элементами списка, а при реализации отличаются структурой узлов. Формально дерево можно определить (рекуррентно):
Один узел является деревом, этот же узел является корнем. Также выделяют пустое дерево, содержащее Λ(лямду).
Пусть 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.
Длиной пути является число на единицу меньше количества узлов, образующих путь или длиной пути называется космической (не помеченная дуга дерева) или суммой (помеченная дуга дерева).
В ряде задач к каждому узлу (или дуге) может быть поставлено имя и значение (следует их различать). Имя для идентификации элемента дерева, а значение представляет полезную информацию ради которой строится дерево:
- если, существует путь нулевой длины от узла до самого себя.
- если, существует путь из узла А в узел В, то узел А является предком узла В, а В потомком узла А.
Любой узел одновременно является и предком самого себя. Истинным предком или истинным потомком является предок (или потомок) не являющимся таковым самого себя.
Корень – это узел, не имеющий истинного предка. Узлы не имеющих истинных потомков называются листьями.
Под дерево, какого – либо дерева можно определить как узел со всеми его потомками. Высотой узла дерева называется длина самого длинного пути от этого узла до любого из его листьев – потомка. Высота дерева совпадает с высотой корня. Глубина узла – длина пути от корня до этого узла при этом путь истинен.
Порядок узлов
Рассмотрим три дерева, они состоят:
Из одного и того же множества элементов А,В,С – имена и значения метки. В отличаются от А и С отношением предок потомок. В варианте а) и б) одинаковые отношения предок потомок, эти деревья можно считать одинаковыми, если не различать положение сыновей и детей, такое дерево называется не упорядоченным.
В упорядоченном дереве все узлы упорядочены слева на право (под упорядочивание не понимается сортировка, а лишь линейная последовательность их следования). Вообще упорядочивание слева на право распространяется и для узлов не связанных отношений предок потомок.
Правило определение расположения узлов: можно прочертить воображаемую форму линию от корня от узла. Узлы находящиеся на линии связан отношение предок потомок и как бы задают отношения порядка сверху вниз, а не слева на право. Это относится также и к сыновьям.