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

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

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

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

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

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

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

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

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

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

TYPE TreeLink = ^Tree;

Tree = record;

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

Left, Right: TreeLink;

End.

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

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

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

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

▪ Антикризисное управление. Конспект лекций

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

▪ Земельное право. Шпаргалка

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

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

<< Назад

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

Питомцы как стимулятор разума 06.10.2025

Помимо эмоциональной поддержки, домашние питомцы могут оказывать заметное воздействие на когнитивные процессы, особенно у пожилых людей. Новое масштабное исследование показало, что общение с кошками и собаками не просто улучшает настроение - оно действительно способствует замедлению возрастного снижения умственных способностей. Работа проводилась в рамках проекта Survey of Health, Ageing and Retirement in Europe (SHARE), охватывающего период с 2004 по 2022 год. В исследовании приняли участие тысячи европейцев старше 50 лет. Анализ показал, что владельцы домашних животных демонстрируют более устойчивые когнитивные функции по сравнению с теми, кто не держит питомцев. Особенно выражен эффект оказался у владельцев кошек и собак. Согласно данным ученых, владельцы собак дольше сохраняют хорошую память, в то время как хозяева кошек медленнее теряют способность к быстрому речевому взаимодействию. Исследователи связывают это с тем, что ежедневное взаимодействие с животными требует внимани ...>>

Мини-ПК ExpertCenter PN54-S1 06.10.2025

Компания ASUSTeK Computer презентовала новый мини-компьютер ASUS ExpertCenter PN54-S1. Устройство ориентировано на пользователей, которым важно сочетание производительности, энергоэффективности и универсальности - от офисных задач до мультимедийных проектов. В основе ExpertCenter PN54-S1 лежит современная аппаратная платформа AMD Hawk Point, использующая архитектуру Zen 4. Это поколение чипов отличается улучшенным управлением энергопотреблением и повышенной вычислительной мощностью. Новинка доступна в конфигурациях с процессорами Ryzen 7260, Ryzen 5220 и Ryzen 5210, представленных AMD в начале 2025 года. Таким образом, устройство охватывает широкий диапазон задач - от базовых офисных до ресурсоемких вычислений. Корпус мини-ПК выполнен из прочного алюминия и имеет размеры 130&#215;130&#215;34 мм, что делает его практически незаметным на рабочем столе или за монитором. Несмотря на компактность, внутренняя компоновка позволяет установить два модуля оперативной памяти SO-DIMM ...>>

Глазные капли, возвращающие молодость зрению 05.10.2025

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

Случайная новость из Архива Wi-Fi на овцах 28.12.2014 Британские исследователи планируют оснастить овец точками доступа Wi-Fi, чтобы провести в сельские районы высокоскоростной доступ в интернет. Носить технику овцам не привыкать: летом 2014 г. они играли роль операторов в "Тур де Франс". Группа исследователей во главе с профессором из Ланкастерского университета Гордоном Блейром (Gordon Blair) планирует изучить возможность установки точек доступа Wi-Fi на овец фермерских хозяйств в британском Уэльсе, сообщает The Daily Mail. По мнению исследователей, это может решить проблему с оснащением высокоскоростным доступом в интернет отдаленных сельских районов. Группа получила на этот проект 171,5 тыс. фунтов стерлингов (околоi14,5 млн). Исследователи предполагают, что оснастить удаленные районы доступом в интернет можно было бы, превратив пасущихся на широких просторах овец в цепочку приемо-передатчиков беспроводного сигнала. "Это может решить проблему типично низких скоростей доступа и плохого сетевого покрытия в большинстве сельских районов Великобритании", - отмечает The Daily Mail. Модули Wi-Fi могут быть интегрированы в цифровые ошейники - устройства для наблюдения за передвижением овец, которые используют фермеры. Добавим, что раньше овец уже использовали в качестве своего рода транспорта для оборудования. В июле 2014 г. этих животных оснастили камерами для съемки престижной велогонки "Тур де Франс", прошедшей в графстве Йоркшир. Камеры на овцах управлялись удаленно. Помимо интернета, команда Блейра будет заниматься изучением проблем загрязнения окружающей среды, наводнений и засух. В рамках проекта будут установлены датчики уровня воды в реках на берегах и датчики атмосферных осадков. Подобная система была установлена в Гондурасе исследователями из Массачусетского технологического института и Microsoft. Авторы проекта попытаются реализовать один из основных принципов "интернета вещей" - способность электронных устройств связываться друг с другом и отправлять данные в интернет без участия человека. Исследователи отмечают, что в сельской местности такую концепцию организовать труднее из-за более сложного ландшафта. Однако и результаты очевидны - качественное сетевое покрытие отдаленных районов и наличие всевозможных датчиков помогут справляться с природными катаклизмами и повысит эффективность сельского хозяйства.

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

▪ Наушники JVC Nearphones HA-NP1T

▪ Расшифрованный помидор

▪ Радиоактивная гроза

▪ Монитор Samsung Odyssey 3D с объемным изображением без очков

▪ Прародина индейцев - Алтай

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

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

▪ раздел сайта Инструменты и механизмы для сельского хозяйства. Подборка статей

▪ статья Этьен Бонно де Кондильяк. Знаменитые афоризмы

▪ статья Какой кавказский народ отчасти состоит из негров? Подробный ответ

▪ статья Бизнес-тренер. Должностная инструкция

▪ статья Лаки для металлов. Простые рецепты и советы

▪ статья Чтение писем в закрытых конвертах. Секрет фокуса

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

www.diagram.com.ua
2000-2025