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.


 

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

76287. Важнейшие группы лимфатических узлов и лимфатические стволы грудной полости 31 KB
  Париетальные: Nodi lymphtici prsternles420 Собирает лимфу от тканей передней грудной стенки плевры перикарда нижние и верхние диафрагмальные узлы сосуды молочной железы и диаф. узлы плечеголовные вены и в левый яремный ствол и в предаортальные лимф. узлы. Отток в ductus thorcicus и шейные узлы .
76288. Грудной лимфатический проток. Главные группы лимфатических узлов и лимфатические стволы брюшной полости 76.49 KB
  Gоясничные лимфатические узлы, nodi lymphoidei lumbales, располагаются забрюшинно около аорты и нижней полой вены (в поясничные лимф узлы оттекает лимфа от нижних конечностей, стенок и органов малого таза, стенок и органов брюшной полости, в частности, в них впадают выносящие сосуды от желудочных, ободочных, брыжеечных, чревных лимфатических узлов). Отток лимфы из поясничных лимфатических узлов осуществляется в правый и левый поясничные стволы, которые дают начало грудному протоку.
76289. Лимфатическое русло и вены нижней конечности 389.82 KB
  Различают поверхностные и глубокие вены нижней конечности имеющие многочисленные клапанынаправляют кровь в глубокие вены между собой соединяются анастомозами коммуникантные вены vv.Поверхностные вены: начинаются из венозных сплетений пальцев стопы которые впадают в тыльную венозную дугу стопы rcus venosus dorslis pedis. От этой дуги берут начало большая и малая подкожные вены ноги.
76291. Лимфатические русло и вены верхней конечности 960.59 KB
  Поверхностные располагаются над поверхностной фасцией и собирают лимфу от кожи и подкожной основы располагаются по ходу подкожных вен и делятся на три группы: Л с латеральной группы: по ходу латеральной подкожной вены впадают в подмышечные л у Л с медиальной группы: по ходу медиальной подкожной вены часть впадает в локтевые часть в подмышечные л у Л с средней группы: лимфа от кожи ладонной поверхности кисти и передней поверхности предплечья. По ходу промежуточной вены предплечья присоединяются к л с латеральной и медиальной групп....
76292. Сердце, cor, cardia 134.14 KB
  По пути к сердцу получает кровь из многих вен. ven cv superior идущая от головы короткая вена впадающая в правое предсердиеи собирающая венозную кровь от верхней части тела от головы шеи и верхних конечностей а также венозную кровь от лёгких и бронхов через бронхиальные вены впадающие сначала в v. hemizygos; частично собирает кровь и от стенок брюшной полости за счёт впадения в неё непарной вены.
76294. Артерии и вены сердца 115.84 KB
  A coronaria dextra – между легочным стволом и правым ушком, затем идет по венечной борозде и заходит назад. То есть, в основном, она снабжает правую половину сердца. Отдает r interventricularis posterior – это конечная ветвь, идет по одноименной борозде до самой верхушки, r marginalis dexter – вниз вдоль правого желудочка по краю.