53446

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

Доклад

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

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

Русский

2014-04-01

22.87 KB

34 чел.

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

Бинарное (Двоичное дерево поиска (англ. 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.


 

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

24403. Нормативная этика 29 KB
  Все моральные учения и этические теории выдвигавшиеся в истории в конечном итоге были посвящены решению практических нравственных проблем. И каждый теоретик посвоему обосновывал моральные представления того обва и класса духовным выразителем интересов крого он выступал хотя субъективно стремился к созданию беспристрастной теории возвышающейся над различными моральными позициями. края содержит моральные оценки и предписания но не может быть научной и метаэтику края является якобы строго научной теорией очищенной от моральных...
24404. Деловое общение 42 KB
  Дейл Карнеги еще в 30е годы заметил что успехи того или иного человека в его финансовых делах даже в технической сфере или инженерном деле процентов на пятнадцать зависят от его профессиональных знаний и процентов на восемьдесят пять от его умения общаться с людьми в этом контексте легко объяснимы попытки многих исследователей сформулировать и обосновать основные принципы этики делового общения или как их чаще называют на Западе заповеди personal public relation весьма приближенно можно перевести как деловой этикет. Только поведение...
24405. Системы этического знания: теоретическая и нормативная этика 102 KB
  Системы этического знания: теоретическая и нормативная этика. Этика наука изучающая феномен морали. Слово этика от греч. В целом же слова этика мораль нравственность продолжают употребляться как взаимозаменяемые.
24406. Система этического знания 30 KB
  Этика обычай нрав характер это совокупность принципов и норм поведения принятых в данной эпохе и в данной социальной среде. Этика зарождается в обществе как результат осознания роли и сущности моральных отношений и в развитом состоянии представляет собой науку о морали содержащую две составляющих: теоретические исследования теоретическая этика и нормативные разработки нормативная этика. Теоретическая этика исследует происхождение и сущность морали ее роль и место в обществе функции механизм действия ее...
24407. Профессиональная этика. Этика управления. Взаимоотношения руководителя и подчиненных 32.5 KB
  Профессиональная этика. Этика управления. Профессиональная этика это совокупность определенных обязанностей и норм поведения поддерживающих моральный престиж профессиональных групп в обществе. Профессиональная этика вырабатывает нормы стандарты требования характерные для определенных видов деятельности.
24408. Этика делового общения 34 KB
  Этика делового общения Умение вести себя с людьми надлежащим образом является одним из важнейших если не важнейшим фактором определяющим шансы добиться успеха в бизнесе служебной или предпринимательской деятельности. В этом контексте легко объяснимы попытки многих исследователей сформулировать и обосновать основные принципы этики делового общения Джен Ягер выделяет шесть следующих основных принципов: 1. Во втором случае оно проходит с помощью переписки или технических средств а первом при непосредственном контакте субъектов общения....
24409. Деловой этикет - это установленный порядок поведения в сфере бизнеса и деловых контактов 34.5 KB
  Деловой этикет это установленный порядок поведения в сфере бизнеса и деловых контактов. Деловой этикет включает в себя следующие разделы: Технологии невербального общения: жесты хорошего тона походка как правильно сидеть вход и выход из автомобиля рукопожатие и пр. Этикет если понимать его как установленный порядок поведения помогает избегать промахов или сгладить их доступными общепринятыми способами. Поэтому основную функцию или смысл этикета делового человека можно определить как формирование таких правил поведения в обществе...
24410. Имидж и его свойства 41 KB
  Имидж складывается в ходе личных контактов человека на основе мнений высказываемых о нем окружающими. Многие индивиды от природы обладают привлекательным имиджем наделены обаянием. Однако отсутствие внешней привлекательности не должно мешать созданию благоприятного имиджа.
24411. Архитектура безопасности. Модели безопасности ее оценки. Общие критерии 44.5 KB
  Данные файла занимают весь первый кластер и только один байт второго остальная же часть второго кластера ничем не заполнена однако недоступна для других файлов эта незанятая область поанглийски называется slack. В следующем доступном кластере могут размещаться данные другого файла. Если под данные этого файла не хватит второго кластера файл будет продолжен в следующем доступном кластере. DOS использует FAT для хранения информации необходимой для доступа к файлам записанным на диске.