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

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

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

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

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

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

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

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

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

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

TYPE TreeLink = ^Tree;

Tree = record;

Inf: <тип данных>;

Left, Right: TreeLink;

End.

Автор: Цветкова А.В.

<< Назад: Древовидные структуры данных

>> Вперед: Примеры реализации операций

Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:

▪ Неорганическая химия. Шпаргалка

▪ Психология развития и возрастная психология. Конспект лекций

▪ Детская хирургия. Шпаргалка

Смотрите другие статьи раздела Конспекты лекций, шпаргалки.

Читайте и пишите полезные комментарии к этой статье.

<< Назад

Последние новости науки и техники, новинки электроники:

Большой адронный коллайдер прекращает работу 16.01.2026

Физика элементарных частиц - одна из самых передовых областей науки, где каждый эксперимент может изменить наше понимание мироздания. Центральным инструментом этих исследований является Большой адронный коллайдер (LHC), уникальный ускоритель частиц, позволяющий изучать самые фундаментальные законы природы. Недавно стало известно, что LHC временно прекращает свою работу для масштабной модернизации, которая подготовит его к новому этапу экспериментов с гораздо большей производительностью. Коллайдер, расположенный в подземном тоннеле вдоль швейцарско-французской границы, создает столкновения частиц на невероятно высоких энергиях. Именно здесь в 2012 году ученые открыли бозон Хиггса - ключевую частицу, объясняющую, почему другие элементарные частицы имеют массу. Это открытие стало одним из самых значимых событий современной физики и подтвердило предсказания Стандартной модели. Причиной временной остановки LHC стало развертывание проекта High-Luminosity LHC (HL-LHC). Модернизация позв ...>>

Робот-бармен AI Barmen 16.01.2026

Американские инженеры создали AI Barmen - робота-бармена, способного не только готовить коктейли, но и запоминать предпочтения гостей. AI Barmen представляет собой автономную систему, которую можно устанавливать практически в любых местах - от баров и ресторанов до гостиниц, аэропортов и корпоративных мероприятий. Робот сочетает механический манипулятор с интеллектуальной программой, которая подбирает напитки на основе истории заказов конкретного пользователя. Гости могут оставаться анонимными или разрешить системе запоминать их вкусы, что позволяет получать одинаково качественный персонализированный коктейль в любой точке, где установлен AI Barmen. Робот готовит широкий спектр коктейлей с высокой точностью, контролирует запасы ингредиентов и автоматически ведет учет, что снижает затраты и минимизирует ошибки. Для работы устройства достаточно стандартной розетки, подключение к воде не требуется, что делает его мобильным и удобным для эксплуатации в самых разных условиях. Систе ...>>

Стерильного нейтрино не существует 15.01.2026

В физике элементарных частиц поиск новых, пока не обнаруженных объектов играет ключевую роль в понимании устройства Вселенной. Иногда такие поиски приводят к громким открытиям, а иногда - к не менее важным отрицательным результатам, которые позволяют отбросить неверные направления. Именно к таким случаям относится недавний вывод ученых о судьбе стерильного нейтрино - одной из самых интригующих гипотетических частиц последних десятилетий. Исследователи из американской лаборатории Fermilab официально сообщили, что им не удалось найти доказательства существования стерильного нейтрино. К такому выводу пришла команда эксперимента MicroBooNE после многолетнего анализа столкновений нейтрино, которые ранее рассматривались как возможный намек на существование четвертого типа этих частиц. Предполагалось, что стерильное нейтрино взаимодействует с материей исключительно через гравитацию, что делало его крайне трудным объектом для обнаружения. В рамках современной физики нейтрино известны в т ...>>

Случайная новость из Архива Беспилотный дроид S1000 07.01.2014 На выставке CES 2014 представлен оригинальный дрон от DJI Innovations. Конструкция беспилотного летательного аппарата включает современные фотаппараты Canon 5D Mark II или Mark III. Подобные роботы, имеющие небольшие устройства для фото- и видеофиксации, уже не являются сегодня сверхоригинальным решением, однако дроны, которые смогло бы нести на себе достаточно тяжёлую цифровую зеркальную камеру, - пока что в новинку для данной отрасли. Китайская компания DJI Innovations подготовила для CES 8-роторный дрон модели S1000, который был сконструирован специально для перемещения в воздушном пространстве с зеркальным фотоаппаратом Canon 5D Mark II/Mark III. Эти профессиональные зеркальные камеры могут принимать участие в съёмках художественных и документальных фильмов. Идея использования дронов в коммерческих целях охватывает всё большее число фирм. Компания Amazon уже заявила о своих намерениях в будущем использовать беспилотные летательные аппараты для доставки покупок. Представители DJI прекрасно понимают, насколько сегодня велика конкуренция на рынке роботизированных устройств. Фирмы вроде Parrot уже смогли реализовать огромное количество своих летательных аппаратов, оснащенных встроенными камерами, поэтому разработчики из Поднебесной решили повысить планку и создать нечто такое, что не имело бы на сегодня аналогов среди конкурирующих фирм. В DJI Innovations надеются, что режиссеры как новостных событий, так и в области кинематографа всерьёз заинтересуются их "монстром среди дронов", который по праву заслужил такое название из-за своих массивных размеров. Установленное профессиональное оборудование на нём, которое способен поднять S1000 - и есть та ставка, сделанная разработчиками. На данный момент не совсем ясно, чему будет равняться стоимость дрона. Можно лишь провести аналогию с младшей 6-роторной моделью S800, цена которой составляет $6000. Нет точных данных и о дате релиза устройства, однако представители компании указывали на то, что она должна состояться в первом квартале 2014 года. DJI уверены в своем успехе, называя своё детище выбором журналистов и кинематографистов. Также китайская компания заявила, что на данный момент новостные агентства вроде Associated Press и BBC обучают своих журналистов правилам эксплуатации дронов наподобие S1000.

Другие интересные новости:

▪ Стирально-сушильная машина TCL Twin Cabin Q10

▪ Медицинские причины религиозного радикализма

▪ Сетевое авто от Bosch

▪ Раскрыт секрет голубых глаз хаски

▪ Антибиотик из грудного молока

Лента новостей науки и техники, новинок электроники

Интересные материалы Бесплатной технической библиотеки:

▪ раздел сайта Компьютерные устройства. Подборка статей

▪ статья Золотая молодежь. Крылатое выражение

▪ статья Какой президент любил разыгрывать своих гостей, падая с ними на автомобиле в озеро? Подробный ответ

▪ статья Слива домашняя. Легенды, выращивание, способы применения

▪ статья Искусственное дыхание. Энциклопедия радиоэлектроники и электротехники

▪ статья Послушный графин. Секрет фокуса

Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2026