Читать онлайн «Структуры данных. Деревья: Методические указания по курсу ''Языки программирования и методы трансляции'' для студентов 1 и 2 курсов факультета математики, механики и компьютерных наук»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» АМЕЛИНА Н. И. , ЧЕРДЫНЦЕВА М. И. СТРУКТУРЫ ДАННЫХ. ДЕРЕВЬЯ МЕТОДИЧЕСКИЕ УКАЗАНИЯ по курсу «Языки программирования и методы трансляции» для студентов 1 и 2 курсов дневного и вечернего отделений факультета математики, механики и компьютерных наук Ростов-на-Дону 2007 3  Методические указания разработаны сотрудниками кафедры прикладной математики и программирования: кандидатом технических наук, доцентом М. И. Чердынцевой и старшим преподавателем Н. И. Амелиной. В методических указаниях даны основные понятия и определения для деревьев, бинарных деревьев, деревьев поиска и сбалансированных деревьев; приведены примеры реализации на языке Паскаль итеративных и рекурсивных алгоритмов обработки деревьев, а также упражнения для самостоятельной работы. Методические указания предназначены для студентов, изучающих курс «Языки программирования и методы трансляции», и преподавателей, ведущих занятия по «Практикуму на ЭВМ» на 1 и 2 курсах дневного и вечернего отделений факультета математики, механики и компьютерных наук. Печатается в соответствии с решением кафедры прикладной математики и программирования факультета математики, механики и компьютерных наук ЮФУ, протокол № 9 от 31мая 2007г. 4  СОДЕРЖАНИЕ 1 Основные понятия и определения . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Основные операции с двоичными деревьями . . . . . . . . . . . . . . . 9 3. 1 Обход дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3. 2 Обработка узлов дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4 Дерево поиска ( сортировки ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4. 1 Построение дерева поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4. 2 Поиск и включение для дерева сортировки . . . . . . . . . . . . . 24 4. 3 Исключение из дерева поиска . . . . . . . . . . . . . . . . . . . . . . . . 27 5 Сбалансированные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ЛИТЕРАТУРА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5  1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ Деревья, в частности бинарные деревья, представляют собой одну из базо- вых структур данных в программировании. Они используются в компиляторах, системах управления базами данных, файловых системах.