Деревья основные операции над деревьями

Операции над деревьями.

Над деревьями определены следующие основные операции:

• 1) Поиск узла с заданным ключом.
• 2) Добавление нового узла
• 3) Удаление узла ( поддерева ) .
• 4) Обход дерева в определенном порядке:
  • Нисходящий обход ;
  • Смешанный обход ;
  • Восходящий обход.

ПОИСК ЗАПИСИ В ДЕРЕВЕ Нужная вершина в дереве ищется по ключу. Поиск в бинарном дереве осуществляется следующим образом. Пусть построено некоторое дерево и требуется найти звено с ключом X. Сначала сравниваем с X ключ, находящийся в корне дерева. В случае равенства поиск закончен и нужно возвратить указатель на корень в качестве результата поиска. В противном случае переходим к рассмотрению вершины, которая находится слева внизу, если ключ X меньше только что рассмотренного, или справа внизу, если ключ X больше только что рассмотренного. Сравниваем ключ X с ключом, содержащимся в этой вершине, и т.д. Процесс завершается в одном из двух случаев:

• 1) найдена вершина, содержащая ключ, равный ключу X;
• 2) в дереве отсутствует вершина, к которой нужно перейти для выполнения очередного шага поиска.

В первом случае возвращается указатель на найденную вершину. Во втором — указатель на звено, где остановился поиск, (что удобно для построения дерева ). ДОБАВЛЕНИЕ НОВОГО УЗЛА Для включения записи в дерево прежде всего нужно найти в дереве ту вершину, к которой можно «подвести» (присоединить) новую вершину, соответствующую включаемой записи. При этом упорядоченность ключей должна сохраняться. Алгоритм поиска нужной вершины, вообще говоря, тот же самый, что и при поиске вершины с заданным ключом. Эта вершина будет найдена в тот момент, когда в качестве очередного указателя, определяющего ветвь дерева, в которой надо продолжить поиск, окажется указатель NIL ( случай 2 в поиске записи в дереве). ОБХОД ДЕРЕВА. Во многих задачах, связанных с деревьями, требуется осуществить систематический просмотр всех его узлов в определенном порядке. Такой просмотр называется прохождением или обходом дерева. Бинарное дерево можно обходить тремя основными способами: нисходящим, смешанным и восходящим ( возможны также обратный нисходящий, обратный смешанный и обратный восходящий обходы). Принятые выше названия методов обхода связаны с временем обработки корневой вершины: До того как обработаны оба ее поддерева, после того как обработано левое поддерево, но до того как обработано правое , после того как обработаны оба поддерева. Используемые в переводе названия методов отражают направление обхода в дереве: от корневой вершины вниз к листьям — нисходящий обход; от листьев вверх к корню — восходящий обход, и смешанный обход — от самого левого листа дерева через корень к самому правому листу. Схематично алгоритм обхода двоичного дерева в соответствии с нисходящим способом может выглядеть следующим образом:

• 1. В качестве очередной вершины взять корень дерева. Перейти к пункту 2.
• 2. Произвести обработку очередной вершины в соответствии с требованиями задачи. Перейти к пункту 3.
• 3.а) Если очередная вершина имеет обе ветви, то в качестве новой вершины выбрать ту вершину, на которую ссылается левая ветвь, а вершину, на которую ссылается правая ветвь, занести в стек; перейти к пункту 2;
• 3.б) если очередная вершина является конечной, то выбрать в качестве новой очередной вершины вершину из стека, если он не пуст, и перейти к пункту 2; если же стек пуст, то это означает, что обход всего дерева окончен, перейти к пункту 4;
• 3.в) если очередная вершина имеет только одну ветвь, то в качестве очередной вершины выбрать ту вершину, на которую эта ветвь указывает, перейти к пункту 2.
• 4. Конец алгоритма.

Для примера рассмотрим возможные варианты обхода дерева (рис. 4.1). При обходе дерева представленного на рис.1 этими тремя методами мы получим следующие последовательности: ABCDEFG ( нисходящий ); CBAFEDG ( смешанный ); CBFEGDA ( восходящий ). Рис.4.1. Схема дереваВОСХОДЯЩИЙ ОБХОД Трудность заключается в том, что в этом алгоритме каждая вершина запоминается в стеке дважды: первый раз — когда обходится левое поддерево, и второй раз — когда обходится правое поддерево. Таким образом, в алгоритме необходимо различать два вида стековых записей: 1-й означает, что в данный момент обходится левое поддерево; 2-й — что обходится правое, поэтому в стеке запоминается указатель на узел и признак (код-1 и код-2 соответственно). Алгоритм восходящего обхода можно представить следующим образом:

• 1) Спуститься по левой ветви с запоминанием вершины в стеке как 1-й вид стековых записей;
• 2) Если стек пуст, то перейти к п.5;
• 3) Выбрать вершину из стека, если это первый вид стековых записей, то возвратить его в стек как 2-й вид стековых записей; перейти к правому сыну; перейти к п.1, иначе перейти к п.4;
• 4) Обработать данные вершины и перейти к п.2;
• 5) Конец алгоритма.

Источник

21. Операции над деревьями

Далее будем рассматривать все операции применительно к бинарным деревьям. I. Построение дерева.

Приведем алгоритм построения упорядоченного дерева.

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

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

3. При удалении узла из дерева следует быть внимательным. Если удаляемый узел является листом, или же имеет только одного потомка, то операция проста. Если же удаляемый узел имеет двух потомков, то необходимо будет найти узел среди его потомков, который можно будет поставить на его место. Это нужно в силу требования упорядоченности дерева.

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

II. Поиск узла с заданным значением ключевого поля.

При осуществлении этой операции необходимо совершить обход дерева. Необходимо учитывать различные формы записи дерева: префиксную, инфиксную и постфиксную.

Возникает вопрос: каким образом представить узлы дерева, чтобы было наиболее удобно работать с ними? Можно представлять дерево с помощью массива, где каждый узел описывается величиной комбинированного типа, у которой информационное поле символьного типа и два поля ссылочного типа. Но это не совсем удобно, так как деревья имеют большое количество узлов, заранее не определенное. Поэтому лучше всего при описании дерева использовать динамические переменные. Тогда каждый узел представляется величиной одного типа, которая содержит описание заданного количества информационных полей, а количество соответствующих полей должно быть равно степени дерева. Логично отсутствие потомков определять ссылкой nil. Тогда на языке Pascal описание бинарного дерева может выглядеть следующим образом:

Данный текст является ознакомительным фрагментом.

Читайте также

14.4.2. Функции управления деревьями

14.4.2. Функции управления деревьями Только что описанные операции соответствуют следующим функциям:#include <search.h> /* XSI */void *tsearch(const void *key, void **rootp,int (*compare)(const void*, const void*));void *tfind(const void *key, const void **rootp,int (*compare)(const void*, const void*));void *tdelete(const void *key, void **rootp,int (*compare)(const void*, const void*));typedef enum

16.1. Операции tty

16.1. Операции tty Устройства tty предоставляют огромное количество опций обработки данных; они относятся к наиболее сложным устройствам ядра. Настраивать можно опции обработки входных и выходных данных, а также потока данных. Также можно контролировать ограниченное

Код операции MI

Код операции MI В таблице 4.14 показано назначение битов кода операции MI. Бит 3 задает вычислительный или невычислительный формат команды. Во втором случае функция, которая должна быть выполнена, закодирована в битах 5-15 кода операции. Функция, выполняемая вычислительной

Операции

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

Проект участка с деревьями и кустарниками в программе 3D Home Architect Design Suite Deluxe

Проект участка с деревьями и кустарниками в программе 3D Home Architect Design Suite Deluxe Рассмотрим пример создания проекта с деревьями и кустарниками в программе 3D Home Architect Design Suite Deluxe. Добавим растительность – деревья и кустарники в проект, созданный в программе.Откройте программу 3D

2. Операции над деревьями

2. Операции над деревьями Далее будем рассматривать все операции применительно к бинарным деревьям.I. Построение дереваПриведем алгоритм построения упорядоченного дерева.1. Если дерево пусто, то данные переносятся в корень дерева. Если же дерево не пусто, то

14.8. Работа с файлами, каталогами и деревьями

14.8. Работа с файлами, каталогами и деревьями При выполнении рутинных задач приходится много работать с файлами и каталогами, в том числе с целыми иерархиями каталогов. Немало материала на эту тему вошло в главу 4, но кое-какие важные моменты мы хотим осветить

Операции += и -=

Операции += и -= Если вы изучаете C#, уже имея опыт использования C++, то можете обратить внимание на отсутствие возможности перегрузки операторных сокращений, включающих операцию присваивания (+=, -= и т.д.). Не волнуйтесь, в C# операторные сокращения с присваиванием

Операции

Операции В языке Си предусматриваются поразрядные логические операции и операции сдвига. Далее мы будем записывать значения в двоичном коде, чтобы вы могли видеть, как выполняются операции. В реальных программах используются целые переменные или константы, записанные в

Операции

Операции Теперь рассмотрим, что можно и нельзя делать с величинами типа enum. Вы можете присвоить константу типа enum переменной того же типа enum feline pet;pet = tiger;Нельзя использовать другие операции присваивания: pet += cat; /* недопустимо */Можно провести сравнение с целью выявления

Операции

Операции Операции в языке Си имеют либо один операнд (унарные операции), либо два операнда (бинарные операции), либо три (тернарная операция). Операция присваивания может быть как унарной, так и бинарной (см. раздел 4.4).Существенным свойством любой операции является ее

4.3. Операции сравнения и логические операции

4.3. Операции сравнения и логические операции Символ операции Значение Использование ! Логическое НЕ !expr меньше exprexpr = Меньше либо равно expr=expr больше exprexpr = больше либо равно expr=expr == равно expr==expr != не равно expr!=expr логическое

9.2. Представление множеств двоичными деревьями

9.2. Представление множеств двоичными деревьями Списки часто применяют для представления множеств. Такое использование списков имеет тот недостаток, что проверка принадлежности элемента множеству оказывается довольно неэффективной. Обычно предикат принадлежит( X, L)

Глава 10 Усовершенствованные методы представления множеств деревьями

Глава 10 Усовершенствованные методы представления множеств деревьями В данной главе мы рассмотрим усовершенствованные методы представления множеств при помощи деревьев. Основная идея состоит в том, чтобы поддерживать сбалансированности или приближенную

Операции is и as

Операции is и as Операция is предназначена для проверки того, имеет ли классовая переменная указанный динамический тип. Операция as позволяет безопасно преобразовать переменную одного классового типа к другому классовому типу (в отличие от явного приведения классового

Источник