q^.next:=p^.next;
p^.next:=q;
q^.prev:=p
End;
q^.inf:=a;
p:=p^.next
End;
5. Вилучення. Як і в попередніх випадках видалення елементу не потребує складного пошуку із порівнянням через один елемент, як у однонапрямлених списках.
write('введіть елемент, який потрібно вилучити');
Readln(a);
p:=first;
while p<>nil do
Begin
if p^.inf=a then
Begin
if p=first then
Begin
first:=p^.next;
p^.prev:=nil
End
Else
Begin
if p^.next<>nil then
Begin
p^.next^.prev:=p^.prev;
p^.prev^.next:=p^.next^.next
End
Else
Begin
p^.prev^.next:=nil
End;
End;
End
Else
p^.prev^.next:=p;
p:=p^.next
End;
Тема: Бінарні дерева.
Особливим видом розгалужених списків є дерева. Особливістю таких динамічних структур даних є те, що кожен елемент має декілька вказівних полів (бінарні, тернарне, п-арні дерева).
На відмінну від двонапрямлених списків, дерева не мають лінійної структури. Підлеглість елементів має розгалужену структуру – це означає, що такі списки мають один верхній елемент – голову. Він має декілька підлеглих елементів, які в свою чергу мають декілька елементів, причому на будь-якому рівні всі вказівники повинні бути зв’язані з іншими елементами, якщо ж ні, то в таких випадках вони вказують в nil.
Доступ до елементів дерева здійснюється послідовно з вершини дерева через фіксований вказівник top. Елементи дерева, обидва вказівники яких зв’язані із підлеглими елементами, називають вузловими вершинами або гілками. Елементи дерева, обидва вказівники яких вільні, називаються листками або висячими вершинами. Елементи дерева, один з вказівників яких вільний, називаються напівисячими вершинами.
Шириною бінарного дерева називається кількість вузлів від крайнього лівого до крайнього правого елементу. Висотою бінарного дерева називається максимальна кількість рівнів елементів від вершини дерева до найдальшого листка.
Бінарні дерева заповнюються не довільним чином або у порядку слідування елементів, а за алгоритмом, який формує їх у вигляді впорядкованої структури.
В якості вершини дерева завжди розміщується перший по-порядку елемент. Кожен новий елемент дерева розміщується у ньому так, щоб він опинився лівіше від поточної вершини, якщо він менший від неї; і правіше, якщо він більший від неї.
Як видно з розглянутого алгоритму, структура бінарного дерева залежить від порядку введення елементів.
Оголошуються бінарні дерева подібно до лінійних списків, у вигляді вказівного типу на елемент дерева. Елемент дерева матиме три поля: інформаційне довільного типу і два вказівних відповідно на лівий і правий елементи.
Дата добавления: 2015-09-11; просмотров: 77 | Поможем написать вашу работу | Нарушение авторских прав |