53446

Операции над бинарными деревьями

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-04-01

22.87 KB

37 чел.

Операции над бинарными деревьями.

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

На рисунке показан наиболее часто встречающийся способ представления бинарного дерева. Оно состоит из девяти узлов. Корнем дерева является узел А. Левое поддерево имеет корень В, а правое поддерево - корень С. Они соединяются соответствующими ветвями, исходящими из А. Отсутствие ветви означает пустое поддерево. Например, у поддерева с корнем С нет левого поддерева, оно пусто. Пусто и правое поддерево с корнем Е. Бинарные поддеревья с корнями D, G, H и I имеют пустые левые и правые поддеревья. Узел, имеющий пустые правое и левое поддеревья, называется листом. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правое и левое поддеревья, то дерево называется строго бинарным. Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку. Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева.

Номер корня всегда равен 1, левый потомок получает номер 2, правый - номер 3. Левый потомок узла 2 должен получить номер 4, а правый - 5, левый потомок узла 3 получит номер 6, правый - 7 и т.д. Несуществующие узлы не нумеруются, что, однако, не нарушает указанного порядка, так как их номера не используются. При такой системе нумерации в дереве каждый узел получает уникальный номер.

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

Почти полное бинарное дерево определяется как бинарное дерево, для которого существует неотрицательное целое k такое, что:

1) каждый лист в дереве имеет уровень k или k+1;

2) если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.Итак, какие же основные операции определены над деревом? Их несколько:

Поиск узла с заданным ключом. Добавление нового узла. Удаление узла (поддерева). Обход дерева в определенном порядке: Нисходящий обход.

Восходящий обход. Смешанный обход. Поиск глубины.

Бинарное дерево поиска предусматривает операции поиска, вставки и удаления элементов по ключу. Используя эти операции можно построить любое бинарное дерево. Операции вставки, удаления и поиска элементов для бинарного дерева используют правило двоичного поиска при доступе к элементу с заданным значением ключа. Необходимо отметить структурную зависимость бинарного дерева от порядка поступления и удаления элементов. Например, при последовательных вставках элементов со строго возрастающими ключами, структура бинарного дерева выродится в линейный список правых сыновей. Важной операцией для бинарного дерева является перебор его элементов в определенном порядке для выполнения какой–либо операции. Также для BST - дерева используются ряд вспомогательных операций, позволяющих воспроизводить операции, характерные для упорядоченных таблиц поиска: доступ к k - му элементу, поиск следующего или предыдущего по ключу элемента, разбиение таблицы на две части, объединение двух таблиц в одну и другие.

Наиболее часто к бинарным деревьям применяют следующие операции (функции). Если Р указатель на узел U, то: Info(P) - возвращает содержимое узла с указателем Р;

Left(P) - возвращает указатель на левого сына узла с указателем Р;

Right(P) - возвращает указатель на правого сына;

Father(P) - возвращает указатель на отца узла с указателем Р;

Brother(P) - возвращает указатель на брата узла с указателем Р;

IsLeft(P) - возвращает true, если узел с указателем Р - левый сын;

IsRight(P) - возвращает true, если узел с указателем Р - правый сын.

HasChildren (P) - возвращает true, если у узла с указателем P есть потомки;

При создании бинарных деревьев используют функции: MakeTree(X) - создает новое бинарное дерево, состоящее из одного узла с информационным полем Х и возвращает указатель этого узла.

SetLeft(P, X) - где Р - указатель узла U, не имеющего левого сына. Создает новый левый сын узла U с информационным полем Х.

SetRight(P, X) - для правого узла, по аналогии с SetLeft.


 

А также другие работы, которые могут Вас заинтересовать

85307. Системы исходных понятий народной художественной культуры 37.16 KB
  Основными понятиями являются культура ценности традиция этническая культура. Ценности первым кто ввел это понятие в научный оборот был польский психолог В. Для большинства исследователей понятие ценности сродни понятию установка. Клакхон ценностиэто осознанное или неосознанное характерное для индивида или группы индивидов представления о желаемом которое определяет выбор целей с учетом возможных последствий.
85308. Календарные праздники и обряды: структура, функции, художественные элементы 35.95 KB
  Основные зимние праздники приходились на январь. Дети девушки и парни под Рождество ходили по домам колядовать Колядовали и в Новый год. Молодежь наряжалась стариками и старухами цыганами гусарами; мазали лица сажей надевали вывороченные наизнанку шубы и ходили по деревне подшучивая над всеми разыгрывая сценки веселясь. Ходили друг к другу в гости обильно угощались блинами оладьями пирогами была и выпивка.
85309. Календарные праздники и обряды на Руси; их связь с зимним и летним солнцеворотами; весенним и осенним равноденствием; с циклами сельскохозяйственных работ; с языческими и христианскими основами веры 35 KB
  Важнейшие на Руси языческие обряды и праздники были слиты с земледельческим трудом с жизнью природы а значит с мифологическими олицетворениями природных сил. Первыми еще в глубокой древности возникли праздники связанные с земледельческим календарем предков восточных славян. Начинаясь в декабре когда солнце поворачивается на лето предвещая скорое пробуждение кормилицы материземли от зимнего сна и заканчиваясь осенью с завершением уборки урожая праздники составляли целостный календарный цикл.
85310. Система церковных праздников 35.79 KB
  Среди двунадесятых праздников три подвижных: Вход Господень в Иерусалим за неделю до Пасхи Вербное воскресенье Вознесение Господне Вознесение в 40й день по Пасхе и день Святой Троицы Пятидесятница Троица в 50й день по Пасхе. Неподвижные великие праздники: Крещение Господне Богоявление Водокрещи Иордань 619 января; Сретение Господне Сретение 215 февраля; Благовещение Пресвятой Богородицы Благовещенье 25 марта 7 апреля; Преображение Господне второй Спас Спас на горе средний Спас Спас яблочный 619...
85311. Классификация традиционных календарных праздников и обрядов русского народа 37.14 KB
  Расписное яйцо было столь важным атрибутом обрядов что длительное время примерно с Х века держался обычай пользоваться специально изготовленными керамическими разукрашенными яйцами писанками. Для землепашца это время критическое все что мог он на полях сделал брошенное зерно дало всходы теперь все зависело от природы а значит от прихоти управляющих природными стихиями существ. И ожидали в это время от русалок не только шалостей и козней но и орошения полей живительной влагой способствующей колошению хлебов. Во время праздника...
85312. Функции фольклора 29.24 KB
  Функции фольклора в целом и отдельных его жанров не могли не изменяться в зависимости от общих изменений структуры всей духовной культуры от типа соотношения фольклорных и условно говоря ldquo;нефольклорныхrdquo; форм и видов духовной культуры. Важнейшие общественные функции фольклора функции народной истории народной философии народной социологии.
85313. Методология и методы изучения народной художественной культуры 33.46 KB
  Виды научных исследований в области НХТ. Теоретические исследования НХК выявление сущности принципов функций закономерностей развития НХТ и т. Фольклористические исследования фиксирующие образцы НХТ выявляющие особенности жанров сказки песни театральные тексты и т. Понятие модели в педагогике возможности педагогического моделирования в разработке направлений развития объединений и организаций занимающихся НХТ.
85314. Традиционное народное жилище: структура, функции 44.65 KB
  Кочевой образ жизни издавна определил тип герметически замкнутого компактного жилищасборноразборной сооружения из решетчатого каркаса и войлочного покрытия круглого в основания и полусферическим верхом. Остов стен составляется из связанных между собой складных деревянных решёток которые определяют размеры и вместимость жилища. Если северная часть считалась почётной то южное пространство примыкающая к двери самая низшая часть жилища. Таким образом круглая юрта оригинальный исторически сложившийся образец жилища идеально...
85315. Научные предпосылки формирования курса «Теория и история народной художественной культуры» 35.12 KB
  Этнология сравнительная дисциплина целью которой является описание культуры а изначально и физических обличий между народами и объяснение таких различий по средствам реконструкции истории развития народов миграции и взаимодействия этносов. Эта концепция рассматривает происхождение культуры и культурных элементов в первобытном состоянии человечества. История культуры представляется как непрерывный процесс прямолинейный процесс перехода от простого к более сложному.