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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

▪ Общая теория статистики. Конспект лекции

▪ Терия организации. Шпаргалка

▪ История мировых религий. Конспект лекций

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

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

<< Назад

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

Тающие айсберги создают новые оазисы жизни на дне океана 30.06.2026

Глобальное потепление активно меняет облик нашей планеты, и одним из наиболее заметных его проявлений становится ускоренное таяние ледников в полярных регионах. Этот процесс не только приводит к подъему уровня Мирового океана, но и вызывает цепную реакцию в морских экосистемах, порой создавая неожиданные и парадоксальные последствия. Массовое высвобождение айсбергов из Гренландии - яркий пример того, как климатические изменения перестраивают жизнь в самых глубоких и удаленных уголках океана. Из-за повышения температуры количество айсбергов, откалывающихся от гренландских ледников, стремительно растет. Ученые проанализировали данные за последние 40 лет и установили, что с 2000 года поток ледяных глыб через пролив Фрама увеличился в четыре раза. Об этом сообщает Futurism со ссылкой на исследование специалистов из Технического университета Дании. Такое беспрецедентное нашествие айсбергов представляет серьезную опасность для международного судоходства. Одновременно оно радикально тра ...>>

Робот-тьютор Optio, помошник школьника 30.06.2026

Икусственный интеллект и робототехника все активнее помогают учителям и ученикам, делая обучение более персонализированным и увлекательным. Гуманоидные роботы, способные взаимодействовать с людьми естественным образом, открывают новые возможности для школ, особенно в условиях нехватки педагогических кадров и растущего интереса к технологиям. Одна из таких инновационных инициатив стартовала в американском штате Нью-Йорк. Компания Realbotix запустила своего помощника учителя на базе искусственного интеллекта под названием Optio в Центральном школьном округе Саламанки. Робот выступает в роли тьютора, предлагая персонализированное репетиторство, многоязычную помощь с домашними заданиями и круглосуточную академическую поддержку. По данным Interesting Engineering, проект направлен на повышение вовлеченности учащихся и внедрение передовых технологий в учебный процесс. В рамках пилотной программы школы округа планируют интегрировать человекоподобных роботов в классы. Изначально Optio буд ...>>

Биопрепараты повышают питательную ценность органической гречихи 29.06.2026

В органическом земледелии особое внимание уделяется не только урожайности, но и качественному составу продукции. Потребители все чаще выбирают продукты с высоким содержанием полезных веществ и без следов химических веществ. Исследования показывают, что применение биологических препаратов может существенно улучшить минеральный состав зерновых культур, делая их более ценными с точки зрения питания. В результате полевых экспериментов, проведенных в 2023-2025 годах, ученые установили, что использование биопрепаратов способствует активному накоплению макроэлементов, в частности фосфора и калия, в зерне органической гречихи. Об этом сообщила Леся Крупак из Белоцерковского национального аграрного университета в своей работе "Экологичность и производительность". Наиболее заметный эффект наблюдался при применении гумата калия. В этом случае содержание калия в зерне увеличивалось на 19-21 процент по сравнению с контрольными участками. Такой результат свидетельствует об улучшении работы тра ...>>

Случайная новость из Архива Иммунитет беременных реагирует на пол ребенка 14.02.2017 От женщин можно услышать, что во время беременности они чувствуют, кто у них внутри, мальчик или девочка. Это не выдумки: в некоторых медицинских исследованиях удалось показать, что известные и не очень приятные симптомы, сопутствующие беременности, могут быть сильнее или слабее в зависимости от пола будущего ребенка. Но в чем конкретная причина таких отличий? Аманда Митчелл (Amanda M. Mitchell) и ее коллеги из Университета штата Огайо предположили, что все дело в иммунитете. Плохое самочувствие часто начинается с воспаления, и вот исследователи решили проверить, как на протяжении беременности меняется воспалительный фон у восьмидесяти женщин. Иммунитет управляет воспалением с помощью сигнальных белков цитокинов, и если в организме появляется, например, бактериальная инфекция, иммунные клетки выделяют много цитокинов, чтобы скоординировать атаку против патогена. С другой стороны, если иммунитет "перегрет", если он на пустом месте, без каких-то серьезных причин поддерживает тлеющую воспалительную реакцию, то это можно узнать по фоновому уровню тех же самых цитокинов. Фоновый уровень воспалительных цитокинов в крови беременных от пола ребенка не зависел. Но все менялось при появлении бактерий: у женщин, беременных девочками, иммунные клетки реагировали на инфекцию сильнее, генерируя больше воспалительных молекулярных сигналов. Бактерии в наш организм проникают постоянно, и иммунитет их атаки успешно отражает, не давая развиться полноценной инфекционной болезни. Однако иммунный ответ должен быть соразмерен угрозе, и вот именно из-за чрезмерного усердия иммунитета беременные могут сильнее уставать, сильнее страдать от разных болей, кроме того, у них могут обостряться симптомы хронических заболеваний, вроде астмы, связанных с повышенной иммунной активностью. Наконец, не стоит забывать, что агрессивная иммунная система матери способна навредить самому ребенку. Почему иммунитет становится таким активным «в присутствии девочек», пока не вполне ясно; возможно, виной тому специфические изменения в гормональном фоне, которые происходят именно при вынашивании ребенка женского пола. Но, как бы то ни было, и самим беременным, и врачам, у которых они наблюдаются, необходимо учитывать такие особенности поведения иммунной системы и своевременно предпринимать какие-то иммуноуспокаивающие меры.

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

▪ Гибкие тонкие аккумуляторы на основе фторида никеля

▪ Огурцы для жарки

▪ Космический аромат от NASA

▪ Твердотельный накопитель WD Blue SN500 NVMe

▪ Блоки питания NZXT C Series Bronze

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

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

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

▪ статья Абсолютное оружие. Крылатое выражение

▪ статья С каких пор женщины участвуют в олимпийских играх? Подробный ответ

▪ статья Правовые основы возмещения вреда пострадавшему

▪ статья Изготовление трансформаторов. Энциклопедия радиоэлектроники и электротехники

▪ статья Простая модель складных цветов. Секрет фокуса

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

www.diagram.com.ua
2000-2026