20. Древовидные структуры данных

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

Если использовать рекурсивное определение, предложенное Н. Виртом, то древовидная структура данных с базовым типом t - это либо пустая структура, либо узел типа t, с которым связано конечное множество древовидных структур с базовым типом t, называемых поддеревьями.

Далее дадим определения, используемые при оперировании древовидными структурами.

Если узел y находится непосредственно под узлом х, то узел y называется непосредственным потомком узла х, а x - непосредственным предком узла у, т. е., если узел хнаходится на i-ом уровне, то соответственно узел y находится на (i + 1) - ом уровне.

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

Узлы дерева, у которых не имеется потомков, называются терминальными узлами (или листами дерева). Все остальные узлы называются внутренними узлами. Количество непосредственных потомков узла определяет степень этого узла, а максимально возможная степень узла в данном дереве определяет степень дерева.

Предков и потомков нельзя поменять местами, т. е. связь исходного и порожденного действует только в одном направлении.

Если пройти от корня дерева к некоторому конкретному узлу, то количество ветвей дерева, которое при этом будет пройдено, называется длиной пути для этого узла. Если все ветви (узлы) у дерева упорядочены, то дерево называется упорядоченным.

Частным случаем древовидных структур являются бинарные деревья. Это деревья, в которых каждый потомок имеет не более двух потомков, называемых левым и правым поддеревьями. Таким образом, бинарное дерево - это древовидная структура, степень которой равна двум.

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

Дерево, степень которого больше двух, называется сильноветвящимся.

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

<< Назад: Очереди

>> Вперед: Операции над деревьями

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

▪ История экономики. Конспект лекций

▪ Право интеллектуальной собственности. Шпаргалка

▪ Экономика. Конспект лекций

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

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

<< Назад

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

Питомцы как стимулятор разума 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

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

Случайная новость из Архива 24-разрядный АЦП Analog Devices 30.10.2003 Компания Analog Devices представляет 24-разрядный сигма-дельта аналого-цифровой преобразователь AD7791 с минимальным среди выпускаемых промышленностью АЦП энергопотреблением и превосходной точностью. Потребляя 65 мкА от источника питания, данный преобразователь превосходит своего ближайшего конкурента на 25% по энергопотреблению и в 6 раз по разрешающей способности. Поставляемый в корпусе MSOP-10 и имеющий вполне конкурентоспособную цену данный АЦП также включает в себя входной буфер и внутренний тактовый генератор, что делает его одним из наиболее высокоинтегрированных сигма-дельта АЦП на рынке. Новый 24-разрядный сигма дельта АЦПА07791 также имеет 16-разрядную версию - AD7790. У них имеются дифференциальные входы, которые могут быть буферированы или нет. Скорость обновления данных на выходе устанавливается программно. Есть также АЦП без буфера и с фиксированной частотой обновления данных на выходе 16 6 Гц, 16-ти и 24-разрядные версии - AD7788 и AD7789. Все АЦП представляют собой комбинированные аналого-цифровые приборы для низкочастотных измерительных устройств. Каждый потребляет 65 мкА при напряжении питания 3 В и 75 мкА при напряжении 5 В (при выключенном буфере). Новые сигма-дельта АЦП поставляются в 10-выводных корпусах MSOP.

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

▪ Бактерии-золотодобытчики

▪ Лодочный реактивный двигатель на забортной воде

▪ MAX17061 - драйверы 8-строчных белых светодиодов

▪ Малогабаритная радиостанция MOTOROLA FV500AA

▪ Модули инфракрасных приемников TSOP48xxxxAM

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

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

▪ раздел сайта Истории из жизни радиолюбителей. Подборка статей

▪ статья Шкала Бофорта, приближенная оценка скорости ветра. Основы безопасной жизнедеятельности

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

▪ статья Сборщик изделий из пластмасс. Должностная инструкция

▪ статья Передатчик в инфракрасной линии связи. Энциклопедия радиоэлектроники и электротехники

▪ статья Необыкновенный узел. Секрет фокуса

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

www.diagram.com.ua
2000-2025