Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Теоретические сведения. Массивы, строки, стек, очередь и связанные списки являются линейными структурами данных, в которых каждый внутренний элемент имеет только одного наследника




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

Дерево (Tree) – это структура данных, представленная в виде нелинейного списка и предназначенная для хранения информации в иерархическом виде.

Структура дерева состоит из множества узлов (Nodes), один их которых является начальным – корень дерева (Root). Узлы соединяются между собой ветвями или ребрами (Edges). Каждый узел может иметь несколько наследников (Children). Если узел имеет хотя бы одного наследника, то его называют родителем (Parent). Узел, не имеющий детей, называется листом (Leaf).

 

Рис. 1. Структура дерева общего вида

В отличие от других нелинейных структур данных, каждый узел дерева может иметь только одного родителя и множество наследников. Сыновья узла и сыновья их сыновей называются потомками (Descendants), а родители и прародители – предками (Ancestors). Если узел не является корнем дерева, то он и всего его потомки образуют собственное поддерево (SubTree), а сам он выступает в качестве его корня.

Путь от корня до узла дает такую характеристику как уровень (Level). Уровень корня принят за ноль. Каждый сын корня является узлом 1-го уровня, следующее поколение – 2-го уровня и т.д.

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

Дерево, каждый узел которого имеет не более одного наследника, называется вырожденным, а не более двух – бинарным (рис. 2).

Рис. 2. Структура вырожденного и бинарного деревьев

а) вырожденное дерево; б) бинарное дерево

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

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

1. Прямое (Direct Scan). Проход дерева осуществляется в порядке ‘Node – Children’ (NC).

2. Обратное (Revers Scan). Проход дерева осуществляется в порядке ‘Children – Node' (CN).

3. Поперечное (Level Scan). Проход дерева осуществляется по уровням, начиная с корня.

4. Симметричное. Проход дерева осуществляется в порядке ‘LeftChild – Node – RightChild’ (CN). Полностью может быть реализовано только для бинарных деревьев.

Например, для дерева, представленного на рис. 2, результат прохождения будет следующим:

A B D C E // прямой проход

D B E C A // обратный проход

A B C D E // поперечный проход

D B A C E // симметричный проход

Каждый способ прохода, кроме поперечного, можно организовать, используя механизм рекурсии. Например, алгоритм прямого прохождения будет следующим:

1. Выполняют действия с данными узла, передаваемого в списке параметров.

2. Если узел не является листом, то для всех его детей рекурсивно вызывается тот же самый метод.

Если число узлов в дереве достаточно большое, то рекурсивный вызов метода приводит к большим затратам оперативной памяти компьютера. В этом случае применяются несколько иные алгоритмы, основанные на использовании таких структуры данных как стек или очередь.

Поперечное прохождение осуществляется следующим образом:

1. Шаг инициализации. В очередь помещают корень дерева.

2. Шаг итерации. Удаляют из очереди элемент и, если он не является листом, то в очередь помещают всех его детей.

3. Шаг выхода. Повторяют шаг 2 до тех пор, пока очередь не окажется пустой.

Обратное прохождение дерева реализуется с помощью стека:

1. Шаг инициализации. В стек помещают корень дерева и все первые дочерние узлы его левой ветви.

2. Шаг итерации. Из стека удаляют элемент, и если он не является последним в списке своего родителя, то в стек помещают его следующего брата и все первые дочерние узлы левой ветви братового поддерева.

3. Шаг выхода. Повторяют шаг итерации до тех пор, пока стек не окажется пустым.

Симметричное прохождение дерева осуществляется следующим образом:

1. Шаг инициализации. В стек помещают корень дерева и все первые дочерние узлы его левой ветви.

2. Шаг итерации. Из стека удаляют элемент, и помещают в стек следующий дочерний узел (если он есть) и все первые дочерние узлы левой ветви его поддерева.

3. Шаг выхода. Повторяют шаг итерации до тех пор, пока стек не окажется пустым.

Прямое прохождение дерева реализуется также как и обратное, но вместо стека используют очередь.

Для построения дерева необходимо использовать такую структуру данных как узел. Она может быть реализована в виде пользовательского класса TTreeNode, содержащего все необходимые данные об узле и методы работы с ним.

 


Поделиться:

Дата добавления: 2015-08-05; просмотров: 68; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты