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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

▪ Микробиология. Конспект лекций

▪ Правоведение. Шпаргалка

▪ Бюджетное право. Шпаргалка

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

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

<< Назад

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

Дети, растущие рядом с природой, обретают крепкие кости 02.03.2026

Влияние окружающей среды на здоровье человека становится все более очевидным, особенно в детском возрасте. Новое исследование, опубликованное в журнале JAMA Network Open, показывает, что близость к природе напрямую связана с крепостью костей у детей. Ученые установили, что у детей, чьи дома окружены природными территориями в радиусе 1000 метров на 25% больше обычного, риск развития крайне низкой плотности костей снижается на 65%. Для проведения исследования были проанализированы данные более 300 детей, проживающих в городских, пригородных и сельских районах Фландрии в Бельгии. Плотность костной ткани у детей в возрасте от четырех до шести лет оценивалась с помощью ультразвуковых методов. Такой подход позволил безопасно и точно измерить состояние костей на ранних этапах формирования скелета. При анализе учитывались ключевые факторы, влияющие на рост и развитие детей: возраст, вес, рост, этническая принадлежность и уровень образования матери. На основании этих параметров исследоват ...>>

Самовосстанавливающаяся инфраструктура будущего 02.03.2026

Современные мосты и бетонные конструкции по всему миру сталкиваются с проблемой устаревания и износа. Многие сооружения, построенные до 1980-х годов, постепенно теряют свою несущую способность, что требует дорогого ремонта или полной замены. Недавние разработки ученых из Швейцарских федеральных лабораторий материаловедения и технологий (Empa) предлагают инновационное решение - систему укрепления бетонных конструкций с помощью "умной стали", способной самостоятельно устранять трещины и повреждения. В основе новой технологии лежит арматура из сплава на основе железа с эффектом памяти формы (Fe-SMA). Этот материал обладает уникальным свойством: при нагревании до 190-200 °C стержни стремятся вернуться к своей первоначальной конфигурации. В бетонной конструкции это создает внутреннее напряжение, которое затягивает трещины и выравнивает деформированные элементы, существенно повышая прочность и долговечность сооружений. Актуальность разработки объясняется критическим состоянием инфрастр ...>>

Поцелуи полезны для здоровья 01.03.2026

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

Случайная новость из Архива Скотч без клея 06.09.2003 В Манчестерском университете (Англия) создана клейкая лента без клея. Правда, пока получен лишь маленький кусочек площадью один квадратный сантиметр. Разработчики воспользовались недавно раскрытым секретом геккона. Эта небольшая ящерка шустро бегает по вертикальным поверхностям, включая стекло. Недавно обнаружилось, что лапки геккона покрыты тончайшими волосками, которые, контактируя с любой поверхностью, притягиваются к ней просто за счет межмолекулярных сил. Каждый волосок обеспечивает лишь очень слабое притяжение, но таких волосков многие миллиарды. Сдвигая подошву, чтобы волоски образовали острый угол с поверхностью, геккон отцепляет лапку от поверхности. Методами нанотехнологии исследователи смогли нанести на гибкую полимерную пленку волоски длиной по 2 микрона и толщиной по 0,2 микрона, точно как у природного образца. На квадратном сантиметре их около ста миллионов. Подсчитано, что если сделать перчатку с таким покрытием, человек сможет на одной руке, одетой в такую перчатку, висеть на потолке или стене. Но массовый выпуск подобной пленки пока не планируется: процесс слишком сложен. И непонятно, насколько долго прослужат микроволоски, - у геккона они отрастают по мере стирания.

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

▪ Модули памяти VLP RDIMM DDR4 64 ГБ от Virtium

▪ Смартфон Samsung для слабовидящих людей

▪ Яд против яда

▪ Лавина в батарее

▪ Строить здания по примеру шершней

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

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

▪ раздел сайта Применение микросхем. Подборка статей

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

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

▪ статья Погрузочно-разгрузочные, складские работы с легковоспламеняющимися взрывоопасными и опасными грузами. Типовая инструкция по охране труда

▪ статья Коммутатор двух устройств для LPT порта. Энциклопедия радиоэлектроники и электротехники

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

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

www.diagram.com.ua
2000-2026