Наиболее типичная операция, выполняемая над бинарными деревьями – обход дерева. Обход – это процедура, при выполнении которой каждый узел обрабатывается ровно один раз некоторым единым образом. Обход дерева заключается в разбиении дерева на корень, левое и правое поддеревья и применении к каждому из поддеревьев соответствующей процедуры обработки до тех пор, пока в процессе разбиения не будет получено пустое дерево. Полный обход дерева дает линейную расстановку узлов, что облегчает выполнение многих алгоритмов. Существует три принципа упорядочения, которые естественно вытекают из структуры дерева. Как и саму древовидную структуру, их удобно выразить с помощью рекурсии. Им соответсвуют три левосторонних алгоритма обхода. Нисходящий (прямой) обход выполняется по формуле “корень-левый-правый” (К-Л-П). 1. обработать корневой узел; 2. обойти левое поддерево в нисходящем порядке; 3. обойти правое поддерево в нисходящем порядке. Трасса нисходящего обхода дерева рис. 68: A B C D E F. Восходящий (концевой) обход выполняется по формуле “левый-правый-корень” (Л-П-К). 1. обойти левое поддерево в восходящем порядке; 2. обойти правое поддерево в восходящем порядке; 3. обработать корневой узел. Трасса восходящего обхода дерева рис. 68 C D B F E A . Смешанный (обратный) обход выполняется по формуле “левый—корень-правый” (Л-К-П). 1. обойти левое поддерево в смешанном порядке; 2. обработать корневой узел; 3. обойти правое поддерево в смешанном порядке. Трасса смешанного обхода дерева рис. 68: С B D A E F . Заметим, что при различных алгоритмах обхода порядок обработки терминальных узлов не изменяется (содержимое терминальных узлов в трассах обхода выделено жирным шрифтом).
Поступайте к нам!
Уважаемые абитуриенты! Мы рады приветствовать Вас на нашем сайте и сегодня сообщаем Вам о том, что Вы всё ещё можете подавать заявления и поступать в ВФ МГИУ. Напоминаем, что на некоторые специальности Вы можете поступить по результатам ЕГЭ. Помните, у нас Вы сможете получить прекрасное образование по следующим направлениям: "Прикладная информатика в экономике", "Бухгалтерский учёт, анализ и аудит", Автомобиле- и тракторостроение", "Менеджмент организации"!
