Т.Н.  Ничушкина, А.В. Никитин

Имени Н.Э. Баумана

(национальный исследовательский университет)»

(МГТУ им. Н.Э. Баумана)

Т.Н.  Ничушкина, А.В. Никитин

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

Методические рекомендации к домашнему заданию по теме:

 «Бинарные деревья»

по дисциплине «Информатика»

 

 

Москва 2017

Оглавление

Введение.. 3

1 Дерево синтаксического разбора.. 4

2 Разбор арифметического выражения.. 5

2.1 Формы записи выражений. 5

2.1.1 Префиксная форма записи. 5

2.1.2 Инфиксная форма записи. 6

2.1.3 Постфиксная форма записи. 6

2.2 Алгоритм построения дерева для разбора арифметического выражения без скобок. 6

2.3 Алгоритм построения дерева для разбора арифметического выражения со скобками. 8

3 Пример вычисления арифметического выражения.. 10

3.1 Порядок синтаксического разбора арифметического выражения через стек 10

3.3 Контрольные вопросы.. 12

4 Требования к выполнению домашнего задания.. 12

4.1 Задание. 12

4.2 Указания к выполнению работы.. 13

4.3 Требования к отчету. 13

4.4 Требования к защите. 14

Заключение.. 15

Список рекомендуемой литературы... 16

Приложение А. Варианты заданий 17

 

Введение

Целью домашнего задания по теме «Бинарные деревья», изучаемой в рамках  дисциплины «Информатика» является закрепление материала по динамическим структурам данным и применение этих структур в практике программирования. В домашнем задании изучаются приемы работы с динамическими бинарными деревьями поиска на языке программирования С++. Основное внимание уделяется практическому применению бинарных деревьев, в частности, использование бинарных деревьев для вычисления арифметических выражений. В методических указаниях приводятся краткие теоретические и справочные сведения, необходимые для выполнения домашнего задания. Рассмотрены примеры решения задачи разбора арифметических выражений с применением бинарных деревьев.

Методические рекомендации предназначены для студентов первого курса кафедры ФН11 (Математика и компьютерные науки).

Разбор арифметического выражения

Как транслятор (программа-переводчик, которая преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд) обрабатывает и выполняет арифметические и логические выражения, которые он встречает в программе?

Один из вариантов – представить это выражение в виде двоичного дерева.

Например, выражению (a + b) / (c - d + 1) соответствует двоичное дерево разбора, показанное на рисунке 3.

Рисунок 3 – Двоичное дерево разбора выражения (a + b) / (c - d + 1)

Формы записи выражений

 

Что получается при прохождении таких двоичных деревьев? В зависимости от варианта обхода такого бинарного дерева можно получить разные формы записи выражения.

Префиксная форма записи

 

Прямое прохождение дерева (корень – левое поддерево – правое поддерево) дает

то есть знак операции (корень) предшествует своим операндам. Такая форма записи арифметических выражений называется префиксной.

Инфиксная форма записи

 

Симметричный обход (левое поддерево – корень – правое поддерево) дает запись вида

,

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

Поскольку скобок нет, правильный порядок операций невозможно восстановить по инфиксной записи.

Постфиксная форма записи

 

В трансляторах широко используется постфиксная запись выражений, которая получается в результате обратного обхода (левое поддерево - правое поддерево - корень).

В такой записи знак операции стоит после обоих операндов:

Пример вычисления арифметического выражения

Задание

 

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

Примерные варианты заданий приведены в приложении А.

Требования к отчету

 

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

 

В отчете по домашнему заданию должны быть даны ответы на контрольные вопросы.

 

Отчет по домашнему заданию должен включать в себя:

1. Титульный лист;

2. Цели домашнего задания;

3. Теоретическая часть с ответами на контрольные вопросы;

4. Задание в соответствии с вариантом;

5. Графическое отображение дерева в соответствии с вариантом;

6. Код программы с комментариями;

7. Тесты программы с пояснениями;

8. Выводы.

Требования к защите

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

Заключение

 

В процессе выполнения домашнего задания по теме «Бинарные деревья» студенты получат краткие теоретические и справочные сведения по построению и обработке бинарных деревьев с помощью динамических структур данных. Рассмотрят примеры решения задачи разбора арифметических выражений с применением бинарных деревьев.

В результате выполнения домашнего задания студенты освоят приемы работы с динамическими бинарными деревьями поиска на языке программирования С++. Получат практические навыки применения бинарных деревьев для вычисления арифметических выражений.

 Список рекомендуемой литературы

1. Иванова Г. С. Основы программирования. М.: Издательство МГТУ им. Н.Э. Баумана, 2001. С. 238–253.

2. Г.В. Ваныкина, Т.О. Сундукова Структуры и алгоритмы компьютерной обработки данных /– М: Изд-во Интуит, 2011. – 211 с.

3. Михалкович С. С. Основы программирования: Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы. — Ростов н/Д.: УПЛ ЮФУ, 2007. — 48 с.

4. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1989. – 392 с.

5. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. М.: Изд-во Вильямс, 2001. – 253 с.

6. Ахо А., Хопкрофт Д.,. Ульман Д. Структуры данных и алгоритмы: Пер. с англ. М.:
Издат. дом «Вильямс», 2000. С. 77–99.

7. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и
анализ / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с

8. Керниган Б., Пайк Р. Практика программирования: Пер. с англ. СПб.: Невский диалект, 2001. С. 83–90.

 

 

Приложение А. Варианты заданий

Номер варианта соответствует порядковому номеру студента в алфавитном списке группы.

ВАРИАНТ	ЗАДАНИЕ	ВАРИАНТ	ЗАДАНИЕ
1	(1+ a)*(2-3*(7- b))	16	(3*(x-4)-8)*(6-2*y)
2	(3 *x+4) - (y * 7- (-4 +2))	17	(7/(a+3))/(4-(1+3b))
3	(6- 4*(b+2)/4) /(7-a)	18	(3/f-7)*(4-2*(8*g+5))
4	(8+9*w)/(7*(3-t)-2)	19	(1-(8-5*x))/(3-(7+3*y))
5	(6-3*(z+4)+2)*(5-k)	20	((2*a+5)/3)- 2 *(7-b)
6	(7-n)/(8+2*(9+m)+4)	21	(2-9)*((1+ p)*7)/(k+3)
7	(f+1)*(6/(1+g)+4)	22	(b* (c-7)/3)-5*((4-c)+1)
8	(k*4-2)/(1+8*(h-3))	23	3+((5-m)*3/7+(n-9)*8)
9	(6*(1+3*b))*(7+a)	24	(a-4)*8-(2+b+8/a)/2
10	(9*(a-1))/(4+3/(b+7))	25	(4-k)*(9-5*(z+2)+1)
11	(4/(3+x))*(y/2+7)	26	(8-(2*k+3))/(7/p+4)
12	(2*(m-3))*(3-2*(n+2))	27	(7-2*n*(9+m)+)/(8+4*m)
13	(x/2+7)*(7*(y-4)+3)	28	(3+8/(b+4))/(6*(a-3))
14	(5/p+2)/(4-(3*k+1))	29	(2*(7-t)-4)/ (8+9*w/2)
15	(8*a+2)*((6*b-5)/3)	30	(k -9)* (k+5)/ ((6 + p)*4)

 

 

Имени Н.Э. Баумана

(национальный исследовательский университет)»

(МГТУ им. Н.Э. Баумана)

Т.Н.  Ничушкина, А.В. Никитин