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

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

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

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

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

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

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

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

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

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

TYPE TreeLink = ^Tree;

Tree = record;

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

Left, Right: TreeLink;

End.

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

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

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

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

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

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

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

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

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

<< Назад

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

Рыжий ген и ускоренная эволюция 30.04.2026

Вопрос о том, как и насколько быстро меняется человеческий вид, давно занимает биологов и генетиков. Долгое время считалось, что эволюционные процессы происходят крайне медленно, однако новые данные заставляют пересматривать эти представления. Особенно интересные результаты связаны с изменением частоты редких генетических признаков, включая рыжий цвет волос. Рыжеволосость сегодня остается редкой чертой: ее носители составляют менее 2 процентов мирового населения. Однако анализ древней и современной ДНК показывает, что ген, связанный с этим признаком, за последние примерно 10 тысяч лет стал заметно более распространенным, особенно среди популяций Европы. Более того, вместе с ним исследователи фиксируют и другие изменения в генетическом профиле человека, затрагивающие внешность и физиологические особенности. Среди сопутствующих тенденций, выявленных в генетических данных, отмечается увеличение частоты светлой кожи, снижение вероятности мужского облысения, а также некоторые физиолог ...>>

Нейтринный лазер 30.04.2026

Нейтринный лазер - это гипотетическое устройство, способное управлять потоками одних из самых трудноуловимых частиц во Вселенной. Такая разработка открывает новые горизонты в изучении фундаментальных законов природы и может изменить представления о космосе. Идею нового типа излучателя представили физики из Massachusetts Institute of Technology, предложив лазер, который вместо света генерирует поток нейтрино. Эти частицы, почти не взаимодействующие с материей, настолько слабо проявляют себя, что их часто называют "частицами-призраками". Тем не менее они пронизывают все вокруг: по оценкам, триллионы нейтрино ежесекундно проходят через человеческое тело, не оставляя следа. Несмотря на их колоссальную распространенность во Вселенной, нейтрино остаются одними из наименее изученных частиц. Их крайне сложно регистрировать, а еще сложнее контролировать, поэтому традиционно их получают в крупных установках вроде ядерных реакторов или ускорителей частиц. Такие комплексы требуют огромных за ...>>

Мороженое не такое вредное, как принято считать 29.04.2026

В питании часто встречаются продукты, которые одновременно вызывают удовольствие и сомнения с точки зрения здоровья. К таким относится и мороженое: оно воспринимается как типичный десерт с высоким содержанием сахара и жиров, однако современные научные данные постепенно усложняют это привычное представление. Долгое время считалось, что мороженое не может быть частью рационального питания, однако исследования последних лет показывают более неоднозначную картину. Ученые подчеркивают, что влияние этого продукта на организм зависит не только от его сладости или калорийности, но и от состава, качества ингредиентов и общего образа жизни человека. Одни из наиболее масштабных данных были получены в рамках долгосрочных наблюдений в США, включавших проекты Nurses Health Study, Nurses Health Study II и Health Professionals Follow-Up Study. В этих исследованиях на протяжении 20-40 лет наблюдали примерно 190 тысяч взрослых участников, регулярно собирая данные об их питании, физической активнос ...>>

Случайная новость из Архива Самый мощный суперкомпьютерный центр 28.10.2012 Официально открылся суперкомпьютерный центр Вайоминга (NCAR-Wyoming Supercomputing Center - NWSC) - место, где находится один из мощнейших в мире суперкомпьютеров, выделенных для развития наук о Земле. Ученые из Национального центра атмосферных исследований (NCAR) и университетов страны начинают серию научных проектов на флагманском компьютере центра, позволяющем осуществлять полтора квадриллиона (1 500 000 000 000 000) операций с плавающей запятой в секунду. Эти проекты направлены на широкий спектр вопросов о Земле - от атмосферных возмущений до активности в подземных разломах, которые, в конечном итоге, помогут предсказывать торнадо, ураганы, землетрясения, засухи и другие стихийные бедствия. "Этот центр поможет нам изменить наше представление о природе, в результате чего общество получит огромные выгоды, - говорит Томас Богдан, президент Университета корпорации атмосферных исследований. - Суперкомпьютер позволит улучшить прогнозы и более эффективно защищать население и экономику". Суперкомпьютерный центр открывает перед исследователями небывалые возможности. Они смогут обмениваться сложными моделями и использовать невероятные вычислительные мощности. Доступ к флагманскому вычислительному устройству обещает ученым новые высоты в областях машиностроения, атмосферных, гидрологических и вычислительных науках. Компьютеры, расположенные на площади 153 000 кв. футов, будут доступны по всей территории США. Большинство исследователей будут взаимодействовать с центром удаленно, используя персональный компьютер и интернет. Основные компоненты системы состоят из массивного хранилища данных, высокопроизводительных вычислительных кластеров и системы визуализации данных. Ученые будут использовать передовые ресурсы нового центра, чтобы изучать сложные процессы в атмосфере Земли, ускорить исследования опасных погодных условий, геомагнитных бурь, изменений климата, лесных пожаров и т.д. За последние годы требования к мощности оборудования значительно возросли. Поэтому, придя на смену устаревшим суперкомпьютерам, новый суперкомпьютерный центр предоставляет возможности для расширения будущих суперкомпьютерных технологий. Ожидается, что он будет эффективно использоваться как минимум несколько ближайших десятилетий.

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

▪ Обновление плееров iPod

▪ Обнаружена взаимосвязь между климатом и уровнем преступности

▪ Игровые мониторы MSI QD-OLED

▪ В недрах Земли гелий поможет удержать железо и кислород

▪ Алмазные нанонити эффективнее Li-Ion батарей

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

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

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

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

▪ статья Какое изощренное убийство в фильме о Джеймсе Бонде является ненатуральным? Подробный ответ

▪ статья Фасовщик аптеки. Типовая инструкция по охране труда

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

▪ статья Задающий генератор для преобразования 1 фазной сети в 3-х фазную. Энциклопедия радиоэлектроники и электротехники

[an error occurred while processing this directive] Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2026