Читать онлайн «Бинарные деревья: Задачи, решения, указания. Учебное пособие»

Министерство образования и науки Российской Федерации Федеральное агентство по образованию Федеральное государственное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» М. Э. Абрамян БИНАРНЫЕ ДЕРЕВЬЯ Задачи, решения, указания Ростов-на-Дону 2009  Печатается по решению учебно-методической комиссии факультета математики, механики и компьютерных наук ЮФУ от 27 апреля 2009 г. (протокол № 8) Рецензент: к. ф. -м. н. , доцент С. С. Михалкович Аннотация Учебное пособие «Бинарные деревья» состоит из четырех модулей. Мо- дуль № 1 посвящен анализу содержимого дерева, модуль № 2 — формирова- нию дерева с заданной структурой и преобразованию существующего дерева, в модуле № 3 рассматриваются особенности деревьев с обратной связью и де- ревьев поиска, а в модуле № 4 — особенности деревьев разбора выражений и деревьев общего вида. Наряду с базовыми сведениями о бинарных деревьях в пособии приводятся решения типовых задач. Кроме того, пособие содержит формулировки 100 учебных заданий, выполнение которых позволит закрепить изученный материал. Все задания снабжены указаниями. Пособие предназначено для преподавателей программирования, старше- классников и студентов. Автор: М. Э. Абрамян. © М. Э. Абрамян, 2009 2 Предисловие Предлагаемое пособие посвящено теме «Бинарные деревья». Данная тема является естественным продолжением тем «Рекурсия» и «Динамические струк- туры данных», поскольку, с одной стороны, деревья являются динамическими структурами (подобно линейным структурам — стекам, очередям и спискам, — рассмотренным в [3]), а с другой стороны, при обработке деревьев, как правило, используются рекурсивные алгоритмы. В соответствии с модульной технологией организации учебного материала пособие разбито на 4 модуля, которые включают как основное содержание, так и контрольные разделы (проектное задание и тесты рубежного контроля), по- зволяющие определить уровень усвоения материала. Модуль № 1 посвящен анализу содержимого дерева, модуль № 2 — формированию дерева с заданной структурой и преобразованию существующего дерева, в модуле № 3 рассмат- риваются особенности деревьев с обратной связью и деревьев поиска, а в моду- ле № 4 — особенности деревьев разбора выражений и деревьев общего вида. Наряду с базовыми сведениями о бинарных деревьях в пособии приводятся ре- шения типовых задач. Кроме того, пособие содержит формулировки 100 учеб- ных заданий, выполнение которых позволит закрепить изученный материал. Все задания снабжены указаниями. Заметим, что приведенный набор заданий можно рассматривать как дополнение к ранее опубликованному сборнику задач по программированию [1–3]. Наличие большого количества учебных задач по- зволило представить проектные задания к каждому модулю в виде набора из 24 вариантов, что дает возможность преподавателю снабдить каждого учащего- ся отдельным вариантом проектного задания.