Читаем Информатика и информационные технологии: конспект лекций полностью

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

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

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

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

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

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

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

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

<p>2. Операции над деревьями</p>

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

I. Построение дерева

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

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

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

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

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

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

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

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

TYPE TreeLink = ^Tree;

Tree = record;

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

Left, Right : TreeLink;

End.

<p>3. Примеры реализации операций</p>

1. Построить дерево из n узлов минимальной высоты, или идеально сбалансированное дерево (количество узлов левого и правого поддеревьев такого дерева должны отличаться не более чем на единицу).

Рекурсивный алгоритм построения:

1) первый узел берется в качестве корня дерева.

2) тем же способом строится левое поддерево из nl узлов.

3) тем же способом строится правое поддерево из nr узлов;

nr = n – nl – 1. В качестве информационного поля будем брать номера узлов, вводимые с клавиатуры. Рекурсивная функция, реализующая данное построение, будет выглядеть следующим образом:

Перейти на страницу:

Все книги серии Экзамен в кармане

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

Конспект лекций соответствует требованиям Государственного образовательного стандарта высшего профессионального образования.Доступность и краткость изложения позволяют быстро и легко получить основные знания по предмету, подготовиться и успешно сдать зачет и экзамен.Рассматриваются понятия экономических признаков на макро– и микроуровнях, принципы в тенденциях макро– и микроэкономики, признаки и порядок установления банкротства предприятий, стратегия и тактика антикризисного управления, ключевые факторы антикризисного управления, особое внимание уделено управлению персоналом кризисного предприятия.Для студентов экономических вузов и колледжей, а также тех, кто самостоятельно изучает данный предмет.

Елена Алексеевна Бабушкина , Елена Бабушкина , Людмила Верещагина , Людмила Сергеевна Верещагина , Олеся Бирюкова , Олеся Юрьевна Бирюкова

Маркетинг, PR / Управление, подбор персонала / Финансы и бизнес

Похожие книги

1С: Бухгалтерия 8 с нуля
1С: Бухгалтерия 8 с нуля

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

Алексей Анатольевич Гладкий

Программирование, программы, базы данных / Программное обеспечение / Бухучет и аудит / Финансы и бизнес / Книги по IT / Словари и Энциклопедии
1С: Управление торговлей 8.2
1С: Управление торговлей 8.2

Современные торговые предприятия предлагают своим клиентам широчайший ассортимент товаров, который исчисляется тысячами и десятками тысяч наименований. Причем многие позиции могут реализовываться на разных условиях: предоплата, отсрочка платежи, скидка, наценка, объем партии, и т.д. Клиенты зачастую делятся на категории – VIP-клиент, обычный клиент, постоянный клиент, мелкооптовый клиент, и т.д. Товарные позиции могут комплектоваться и разукомплектовываться, многие товары подлежат обязательной сертификации и гигиеническим исследованиям, некондиционные позиции необходимо списывать, на складах периодически должна проводиться инвентаризация, каждая компания должна иметь свою маркетинговую политику и т.д., вообщем – современное торговое предприятие представляет живой организм, находящийся в постоянном движении.Очевидно, что вся эта кипучая деятельность требует автоматизации. Для решения этой задачи существуют специальные программные средства, и в этой книге мы познакомим вам с самым популярным продуктом, предназначенным для автоматизации деятельности торгового предприятия – «1С Управление торговлей», которое реализовано на новейшей технологической платформе версии 1С 8.2.

Алексей Анатольевич Гладкий

Финансы / Программирование, программы, базы данных

Все жанры