Глава 8. Бинарные деревья.

Глава 8. Бинарные деревья.

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

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

Рисунок 8.1. Бинарное дерево

Теперь рассмотрим случай, когда каждый узел имеет до двух дочерних узлов. Иначе говоря, для каждого узла существует максимум две связи с узлами следующего нижнего уровня. Эта структура называется бинарным деревом. Согласно принятому соглашению, два дочерних узла данного узла называются левым и правым дочерними узлами, поскольку при рисовании дерева с расположением его корня в вершине, дочерние узлы выстраиваются горизонтально под ним, один левее от другого. Классическое представление бинарного дерева показано на рис. 8.1.

Из приведенных рассуждений ясно, что при определении используемого узла бинарного дерева в Delphi-программе нам требуются две связи (т.е. указатели) с его дочерними узлами, связь с его родительским узлом (эта связь необязательна, но, как мы увидим, ее применение упрощает некоторые алгоритмы, работающие с деревьями) и фактические данные, которые должны храниться в узле. С целью упрощения задачи примем, что данные в узле могут быть представлены указателем, подобно TList и структурам данных, которые уже были рассмотрены в этой книге. Поскольку узел имеет фиксированный размер, мы снова воспользуемся описанным в главе 3 диспетчером узлов, когда дело дойдет до создания класса бинарного дерева. Код, приведенный в листинге 8.1, определяет расположение записей узлов.

Листинг 8.1. Расположение узлов в бинарном дереве type

TtdChildType = ( {типы дочерних узлов}

ctLeft, {.. левый дочерний узел}

ctRight);

{.. правый дочерний узел}

TtdRBColor = ( {цвета для красно-черного дерева}

rbBlack, {..черный}

rbRed);

{..красный}

PtdBinTreeNode = ^TtdBinTreeNode;

TtdBinTreeNode = packed record btParent : PtdBinTreeNode;

btChild : array [TtdChildType] of PtdBinTreeNode;

btData : pointer;

case boolean of

false : (btExtra : longint);

true : (btColor : TtdRBColor);

end;

Обратите внимание, что две дочерние связи мы определили в виде двухэлементного массива. На первый взгляд, это может показаться излишним, но когда дело дойдет до реализации операций с бинарным деревом, такое определение существенно упростит нашу задачу. Кроме того, узел бинарного дерева объявляет дополнительное поле, которое не требуется для обычных бинарных деревьев, однако упрощает задачу для красно-черного варианта дерева бинарного поиска.

Создание бинарного дерева

Само по себе создание бинарного дерева тривиально. В простейшем случае корневой узел бинарного дерева определяет все бинарное дерево.

var

MyBinaryTree : PtBinTreeNode;

Если MyBinaryTree равен nil, никакого бинарного дерева не существует, поэтому это значение служит начальным значением бинарного дерева.

{инициализировать бинарное дерево}

MyBinaryTree :=nil;

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Деревья и узлы

Из книги автора

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


Бинарные операторы 

Из книги автора

Бинарные операторы  Бинарными называются операторы, которые соединяют два операнда (табл. П1.4).Таблица П1.4. Бинарные операторы Оператор Описание Оператор Описание - Вычитание / Деление + Сложение % Вычисление остатка от


Бинарные операции

Из книги автора

Бинарные операции gmp_andЛогическое И (AND).Синтаксис:resource gmp_and(resource x, resource y)gmp_orЛогическое ИЛИ (OR).Синтаксис:resource gmp_or(resource x, resource y)gmp_xorЛогическое исключающее-ИЛИ (XOR).Синтаксис:resource gmp_xor(resource x, resource y)gmp_setbinУстановка бита.Синтаксис:resource gmp_setbin(resource &x, int index [, bool


3.1. Структуры и деревья

Из книги автора

3.1. Структуры и деревья Чтобы легче было понять сложную структуру, ее обычно представляют в виде дерева, в котором каждому функтору соответствует вершина, а компонентам соответствуют ветви дерева. Каждая ветвь может указывать на другую структуру, так что мы можем иметь


Глава 9 Деревья и кустарники

Из книги автора

Глава 9 Деревья и кустарники В данной главе описываются примеры проектирования всевозможных растительных форм, а также возможности использования библиотек растительных элементов в некоторых программах. Здесь рассмотрены приложения 3D Home Architect Design Suite Deluxe и


R.13.4.2 Бинарные операции

Из книги автора

R.13.4.2 Бинарные операции Бинарную операцию можно задать с помощью нестатической функции-члена (§R.9.3), имеющей один параметр, или с помощью функции, не являющейся членом, с двумя параметрами. Таким образом, для всякой бинарной операции @ выражение x@y может интерпретироваться


9.3. Деревья

Из книги автора

9.3. Деревья Я не увижу никогда, наверное, Поэму столь прекрасную как дерево. Джойс Килмер, «Деревья»[11] В информатике идея дерева считается интуитивно очевидной (правда, изображаются они обычно с корнем наверху, а листьями снизу). И немудрено, ведь в повседневной жизни мы


Лекция № 5. Реляционная алгебра. Бинарные операции

Из книги автора

Лекция № 5. Реляционная алгебра. Бинарные операции 1. Операции объединения, пересечения, разности У любых операций есть свои правила применимости, которые необходимо соблюдать, чтобы выражения и действия не теряли смысла. Бинарные теоретико-множественные операции


3. Бинарные операции на языке структурированных запросов

Из книги автора

3. Бинарные операции на языке структурированных запросов Как и унарные операции, операции бинарные также имеют свою реализацию на языке структурированных запросов или SQL. Итак, рассмотрим осуществление на этом языке уже пройденных нами бинарных операций, а именно –


Скошенные деревья

Из книги автора

Скошенные деревья Как бы то ни было, ознакомившись с этими операциями простых и спаренных двухсторонних и односторонних поворотов, мы может их использовать в структуре данных, называемой скошенным деревом. Скошенное дерево (splay tree) - это дерево бинарного поиска,


Красно-черные деревья

Из книги автора

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


Деревья

Из книги автора

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


6.2.1 Бинарные и Унарные Операции

Из книги автора

6.2.1 Бинарные и Унарные Операции Бинарная операция может быть определена или как функция член, получающая один параметр, или как функция друг, получющая два параметра. Таким образом, для любой бинарной оперции @ aa@bb может интерпретироваться или как aa.operator@(bb), или как


7.16.2 Бинарные Операции

Из книги автора

7.16.2 Бинарные Операции Бинарная операция может быть определена или с помощью функции члена (см. #8.5.4), получающей один параметр, или с помощью функции друга (см. #8.5.9), получающей два параметра, но не двумя способами одновременно. Так, для любой бинарной операции @, x@y может быть


У15.1 Окна как деревья

Из книги автора

У15.1 Окна как деревья Класс WINDOW порожден от TREE [WINDOW]. Поясните суть родового параметра. Покажите, какое новое утверждение появится в связи с этим в инварианте


У15.7 Деревья

Из книги автора

У15.7 Деревья Согласно одной из интерпретаций, дерево - это рекурсивная структура, представляющая собой список деревьев. Замените приведенное в этой лекции описание класса TREE как наследника LINKED_LIST и LINKABLE новым вариантомclass TREE [G] inheritLIST [TREE [G]]feature ...endРасширьте это описание до