Иерархические структуры данных: бинарные деревья

Федеральное государственное бюджетное 
образовательное учреждение высшего образования 
«Московский государственный технический университет имени Н.Э. Баумана 
(национальный исследовательский университет)»
А.В. Никитин, Т.Н. Ничушкина
Иерархические структуры данных:
бинарные деревья
Учебное пособие

УДК 004.432
ББК 32.81
        Н62
Издание доступно в электронном виде по адресу  
ebooks.bmstu.press/catalog/255/book1914.html
Факультет «Информатика и системы управления»
Кафедра «Компьютерные системы и сети»
Рекомендовано Научно-методическим советом 
МГТУ им. Н.Э. Баумана в качестве учебного пособия
Никитин, А. В.
Иерархические структуры данных: бинарные деревья : учебное 
Н62
пособие / А. В. Никитин, Т
. Н. Ничушкина. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2018. — 54, [2] с.
ISBN 978-5-7038-5005-3
Издание содержит теоретические сведения о разработке и применении 
иерархических структур данных в виде бинарных деревьев на языке С++. 
Приведены примеры основных алгоритмов и программ для работы с бинарными деревьями.
Для студентов первого курса МГТУ им. Н.Э. Баумана, обучающихся по 
программе бакалавриата в рамках направлений подготовки «Математика и 
компьютерные науки», «Информатика и вычислительная техника». 
	
УДК 004.432
	
ББК 32.81
 
	
	
© МГТУ им. Н.Э. Баумана, 2018
© Оформление. Издательство
ISBN 978-5-7038-5005-3	
МГТУ им. Н.Э. Баумана, 2018

ПРЕДИСЛОВИЕ
Учебное пособие предназначено для углубления знаний, полученных студентами при освоении лекционного материала и в 
процессе семинарских занятий, а также для самостоятельного 
изучения ими темы «Иерархические структуры данных: бинарные 
деревья» по дисциплине «Информатика», входящей в основную 
образовательную программу бакалавриата по направлениям подготовки «Математика и компьютерные науки», «Информатика и 
вычислительная техника».
Цель учебного пособия — закрепление теоретических знаний и 
практических навыков, необходимых при разработке алгоритмов 
и программ с использованием иерархических структур данных, 
формирование умений и навыков распознавания таких структур 
и реализации таких алгоритмов.
После изучения темы «Иерархические структуры данных: 

бинарные деревья» дисциплины студенты овладеют:
•
• базовыми знаниями в областях построения иерархических 
структур данных, необходимыми для разработки математических 
моделей объектов и формализации задач разработки сложных программ;
•
• практическими навыками разработки алгоритмов с использованием иерархических структур данных;
•
• приемами тестирования и отладки программ с иерархическими структурами данных, в том числе с приемами рекурсивной 
обработки таких структур.
Планируемые результаты обучения. Студент должен: 
знать
•
• виды бинарных деревьев как одной из разновидностей 

иерархических структур данных;
•
• области практического применения бинарных деревьев;
•
• способы разработки задач с применением основных операций над бинарными деревьями;
•
• способы оценки необходимости в применении иерархических структур данных;
3

уметь
•
• выполнять анализ задачи и обосновывать необходимость 
применения того или иного вида иерархической структуры данных для ее решения в соответствии с классификацией;
•
• разрабатывать алгоритм решения задачи;
•
• выбирать способ реализации иерархической структуры данных на языке С++;
владеть навыками
•
• анализа предметных областей решаемых задач;
•
• оценки содержательной части и получения их формальной 
постановки;
•
• анализа и применения методов решения задач с иерархической структурой данных.
Для изучения указанной темы необходимы знания, умения и 
навыки, полученные обучающимися при освоении школьной 
программы.
Методические указания по освоению материала учебного пособия. 
Основной целью освоения материала учебного пособия является 
самостоятельное изучение студентами темы «Иерархические структуры данных: бинарные деревья».  
Учебное пособие состоит из четырех глав. 
В первой главе разъяснены общие понятия о бинарных деревьях, 
рассмотрены различные их классификации и виды, а также варианты и особенности обхода таких деревьев. Приведена обобщенная 
структура бинарных деревьев, перечислены основные операции 
над деревьями. Даны примеры реализации алгоритмов таких операций.
Во второй главе рассмотрено практическое применение бинарных деревьев: в экспертных системах, в структурах каталогов, при 
разборе и расчете арифметических выражений и при сжатии информации. 
В третьей главе приведены основные принципы работы деревьев семантического разбора, а также описание и примеры реализации 
алгоритма разбора арифметических выражений без скобок и со 
скобками. Представлены некоторые допущения при построении 
дерева по арифметическому выражению. 
В четвертой главе дан пример вычисления арифметического 
выражения через бинарные деревья. Продемонстрирована возможность реализации такого разбора как через стек, так и через бинарные деревья. Определены основные правила вычисления арифме4

тических выражений c помощью бинарных деревьев. Приведены 
примеры программ обработки.
Главы учебного пособия следует прорабатывать последовательно, так как усвоение материала каждой из них обеспечивает успешное восприятие материала последующих глав.
Основные понятия и положения проиллюстрированы примерами, которые необходимо внимательно разобрать. 
В конце каждой главы даны контрольные вопросы. Ответы на 
вопросы позволят обучающемуся самому оценить степень понимания и усвоения им теоретических положений. 
В приложении 1 приведены задачи для решения на семинаре, 
в приложение 2 вынесены основные термины, встречающиеся в 
пособии.
Изучение иерархических структур и алгоритмов их обработки 
очень важно для понимания многих дисциплин профессионального цикла. Приведенные в учебном пособии сведения о структуре данных бинарных деревьев, особенностях ее программирования 
и отладки позволят студентам использовать иерархические структуры данных при решении различных задач, программировать 
такие структуры на языке С++, определять и контролировать 
выполнение и завершение таких программ, выполнять их тестирование и отладку, а также освоить более сложные языки высокого уровня и структуры данных.

ВВЕДЕНИЕ
В языке C++ имеются средства создания динамических структур данных, которые позволяют во время выполнения программы 
образовывать объекты, выделять для них память и освобождать 
память, когда в этих объектах исчезает необходимость. Во многих 
задачах требуется использовать данные, состав и объем которых 
могут изменяться в процессе выполнения программы. Для их 
представления используют динамические структуры.
Ранее в курсе «Информатика» рассматривались информационные структуры, данные в которых располагаются линейно, например, в односвязном списке — от первого узла к единственному 
последнему, в динамическом массиве — в виде непрерывного 
блока. Такие структуры не охватывают всего спектра возможных 
форм представлений данных, имеют линейный вид и единственный 
порядок обхода, который определяет порядок следования (перечисления, логической нумерации) элементов. С их помощью 
сложно описать иерархические структуры, подобные каталогам 
или генеалогическому древу.
В настоящем пособии будет рассмотрена еще одна структура 

данных — дерево. С точки зрения организации данных такие структуры обеспечивают разнообразие вариантов размещения одного и 
того же набора данных, а также различные варианты обхода одной 
и той же структуры. Древовидная структура данных рассмотрена 
на примере бинарных (двоичных) деревьев поиска (binary search 
tree).