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.


 

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

35379. Настройка компютерної системи засобами BIOS SETUP 35 KB
  Виберіть пункт меню STANDART CMOS SETUP і встановіть поточний системний час і дату на 23:59 і 31.12.2008. Яким чином можна виконати аналогічну операцію в ОС Windows? На панелі задач мається часова панель,де і можна змінити час, і дату!
35380. Керування процесом завантаження ОС 1.82 MB
  Мета: Навчитися створювати завантажувальну дискету різними способами; навчитися використовувати її у разі аварійної ситуації в роботі ПК. Використовуючи можливості Windows створіть системну дискету для аварійного завантаження ПК у разі неполадок в її роботі. Які файли при цьому копіюються на дискету Створіть завантажувальну системну дискету командою formt з командного рядка MS DOS. Які файли при цьому копіюються на дискету Створіть завантажувальну системну дискету командою sys з командного рядка MS DOS.
35381. Тема: Робота з вікнами. 1.69 MB
  Практична робота №3 Тема: Робота з вікнами. Мета: ознайомитися із структурою стандартного вікна ОС Windows прийомами роботи з одним і декількома вікнами. представити схематичний малюнок вікна і описати призначення основних його елементів; 3. скрутити і відновити вікно а потім закрити його; пояснити в чому полягає різниця між згортанням і закриттям вікна; Разница между сварачеванием и закрытием окна состоит в том что когда сварачеваеш окно оно остается на панели задач а при закрытие окно закриваеться совсем.
35382. Державне та регіональне управління 3.79 MB
  Державне управління наука, що існує тільки у поєднанні теоретичного і практичного аспектів та вивчає різні види управлінської діяльності - від удосконалення праці державних служіювців до розробки концептуальних напрямків розвитку державних інституцій.
35384. Пространственные зубчатые передачи 677 KB
  Во многих машинах осуществление требуемых движений механизмов связано с необходимостью передавать вращение с одного вала на другой при условии, что оси этих валов либо пересекаются, либо скрещиваются.
35385. Зміст державної політики у сфері охорони здоровя 93 KB
  Система органів управління охороною здоровя населення. Державна політика у галузі охорони здоровя. Шляхи вдосконалення державного управління у сфері охорони здоровя
35386. Тема: Робота з оболонкою Norton Commnder. 116 KB
  Ознайомитися з прийомами роботи у файлових менеджерах на прикладі оболонки Norton Commander.
35387. Тема: Створення файлу конфігурації системи config. 36 KB
  Ознайомитися з основними командами конфігурації системи MS - DOS і на підставі одержаних теоретичних відомостях написати прості файли конфігурації системи.