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

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

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

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

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

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

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

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

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

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

TYPE TreeLink = ^Tree;

Tree = record;

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

Left, Right: TreeLink;

End.

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

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

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

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

▪ Корпоративное право. Шпаргалка

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

▪ Гражданское право. Часть II. Шпаргалка

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

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

<< Назад

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

Лабораторная модель прогнозирования землетрясений 30.11.2025

Предсказание землетрясений остается одной из самых сложных задач геофизики. Несмотря на развитие сейсмологии, ученые все еще не могут точно определить момент начала разрушительного движения разломов. Недавние эксперименты американских исследователей открывают новые горизонты: впервые удалось наблюдать микроскопические изменения в контактной зоне разломов, которые предшествуют землетрясению. Группа под руководством Сильвена Барбота обнаружила, что "реальная площадь контакта" - участки, где поверхности разлома действительно соприкасаются - изменяется за миллисекунды до высвобождения накопленной энергии. "Мы открыли окно в сердце механики землетрясений", - отмечает Барбот. Эти изменения позволяют фиксировать этапы зарождения сейсмического события еще до появления традиционных сейсмических волн. Для наблюдений ученые использовали прозрачные акриловые материалы, через которые можно было отслеживать световые изменения в зоне контакта. В ходе искусственного моделирования примерно 30% ко ...>>

Музыка как естественный анальгетик 30.11.2025

Ученые все активнее исследуют немедикаментозные способы облегчения боли. Одним из перспективных направлений становится использование музыки, которая способна воздействовать на эмоциональное состояние и когнитивное восприятие боли. Новое исследование международной группы специалистов демонстрирует, что даже кратковременное прослушивание любимых композиций может значительно снижать болевые ощущения у пациентов с острой болью в спине. В эксперименте участвовали пациенты, обратившиеся за помощью в отделение неотложной помощи с выраженной болью в спине. Им предлагалось на протяжении десяти минут слушать свои любимые музыкальные треки. Уже после этой короткой сессии врачи фиксировали заметное уменьшение интенсивности боли как в состоянии покоя, так и при движениях. Авторы исследования подчеркивают, что музыка не устраняет саму причину боли. Тем не менее, она воздействует на эмоциональный фон пациента, снижает уровень тревожности и отвлекает внимание, что в сумме приводит к субъективном ...>>

Алкоголь может привести к слобоумию 29.11.2025

Проблема влияния алкоголя на стареющий мозг давно вызывает интерес как у врачей, так и у исследователей когнитивного старения. В последние годы стало очевидно, что границы "безопасного" употребления спиртного размываются, и новое крупное исследование, проведенное международной группой ученых, вновь указывает на это. Работы Оксфордского университета, выполненные совместно с исследователями из Йельского и Кембриджского университетов, показывают: даже небольшие дозы алкоголя способны ускорять когнитивный спад. Команда проанализировала данные более чем 500 тысяч участников из британского биобанка и американской Программы миллионов ветеранов. Дополнительно был выполнен метаанализ сорока пяти исследований, в общей сложности включавших сведения о 2,4 миллиона человек. Такой масштаб позволил оценить не только прямую связь между употреблением спиртного и развитием деменции, но и влияние генетической предрасположенности. Один из наиболее тревожных результатов касается людей с повышенным ге ...>>

Случайная новость из Архива Готовится взрыв дамбы 07.11.2011 Как известно, большая часть территории Голландии находится ниже уровня моря, и страна защищена дамбами, отгораживающими сушу от моря. Близ города Нивесханс на голландско-немецкой границе недавно построена экспериментальная дамба, на которой можно имитировать процесс прорыва плотины и его последствия. В тело плотины и в водосток встроено около 300 датчиков. Нажатием кнопки любой участок дамбы раскрывается, и компьютеры регистрируют процесс экспериментального наводнения. Полученные данные используются для предотвращения таких событий в реальности.

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

▪ Плазменный двигатель для работы в земной атмосфере

▪ Комбинированный привод с двумя лазерами для DVD-дисков

▪ Горы растут в теплом климате

▪ Новый Кубик Рубика сам научит себя собирать

▪ Трекер вещей Huawei Tag

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

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

▪ раздел сайта Акустические системы. Подборка статей

▪ статья Любовь к отеческим гробам. Крылатое выражение

▪ статья Относится ли дельфин к млекопитающим? Подробный ответ

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

▪ статья Антенны УКВ. Справочник

▪ статья Блок питания с защитой от перегрузки по току. Энциклопедия радиоэлектроники и электротехники

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

www.diagram.com.ua
2000-2025