8.1.Двоично дърво.Представяне.Основни операции
8.2.Граф.Представяне.Основни операции
8.3.Пролог и КС-граматики
8.4.Пресмятане на стойност на аритметичен израз
8.5.Интерпретатор на подмножество на езика Пролог
8.1. Двоично дърво. Представяне. Основни операции
Логическо описание
Двоично дърво се нарича структура от данни, която е или празна, или се състои от:
-данна, наречена корен
-двоично дърво, наречено ляво поддърво (ЛПД)
-двоично дърво, наречено дясно поддърво (ДПД)
Възможен е достъп до всеки връх, като достъпът до корена е пряк. Операциите включване и
изключване са допустими при запазване на типа на структурата.
Представяне
Съществуват различни начини за представяне на двоични дървета. Най-ефективен и естествен
начин е като структура, главният функтор на която е атом, различен от корена. За целта са
необходими специален атом за означаване на празното двоично дърво, а също и функтор за построява
не на непразно дърво от корен и поддърва.
Ще направим следния избор:
-Празното дърво ще представяме чрез атома nil.
-За функтор на непразното дърво ще изберем атома bintree. Тогава двоичното дърво с корен Х, с
ляво поддърво L и дясно поддърво R се представя чрез структурата bintree(L, Х, R).
Основни операции
Принадлежност на елемент на двоично дърво
Задача 1. Да се дефинира отношение mem_bin(X, T), което е истина, ако Х е връх на двоичното
дърво Т.
Решение:
Това отношение може да се дефинира чрез следните правила:
Х е връх на двоичното дърво Т, ако:
-Х съвпада с корена на Т, или
-Х е връх на ЛПД на Т, или
-Х е връх на ДПД на Т.
Тогава програмата има вида:
mem_bin(X, bintree(_, X, _)).
mem_bin(X, bintree(L, _, _)) :- mem_bin(X, L).
mem_bin(X, bintree(_, _, R)) :- mem_bin(X, R).
Дефиниция: Празното дърво nil е двоично наредено дърво. Непразно двоично дърво
bintree(L, Х, R) е двоично наредено дърво, ако:
-върховете на ЛПД L са по-малки от Х и
-върховете на ДПД R са по-малки от Х и
-L и R са двоично наредени дървета.
Забележка: Не се допуска дублиране на елементи.
Задача 2. Да се дефинира отношение mem_bin(X, L), което проверява дали елементът Х принадлежи
на двоично нареденото дърво L.
Решение:
Х е връх на двоично нареденото дърво Т, ако:
-Х съвпада с корена на Т, или
-Х е връх на ЛПД на Т, в случай, че Х е по-малко от корена на Т;
-Х е връх на ДПД на Т, в случай, че Х е по-голямо от корена на Т.
Отношението mem_bin може да се дефинира по следния начин:
mem_bin(X, bintree(_, X, _)).
mem_bin(X, bintree(L, K, _)) :- по-голямо(K, X),
mem_bin(X, L).
mem_bin(X, bintree(_, K, R)) :- по-голямо(Х, К),
mem_bin(X, R).
В случая, когато върховете на дървото са числа, отношението по-голямо(К, Х) може да се замени
с К > Х. За лексикографско сравняване се използват инфиксните оператори @<, @=<, @>, @>=.
Включване на елемент в двоично наредено дърво
Задача 3: Да се дефинира отношение input(Т, Х, Т1), което се удовлетворява, ако след включване
на елемента Х в двоично нареденото дърво Т, се получава двоично нареденото дърво Т1.
Решение:
Най-прост начин за дефиниране на отношението input е елементът Х да се включи на най-ниво, т.е.
като листо. Мястото се избира така, че да не се промени наредеността на елементите на дървото.
Правила за включване на елемент Х в двоично наредено дърво Т:
-Резултатът от включването на елемента Х в празното двоично наредено дърво е двоично наредено
то дърво bintree(nil, X, nil).
-Ако Х съвпада с корена на Т, новото двоично дърво, съвпада с Т.
-Ако коренът на Т е по-голям от Х, Х се включва в ЛПД на Т.
-Ако е по-голямо от корена на Т, Х се включва в ДПД на Т.
Тогава input има вида:
input(nil, X, bintree(nil, X, nil)).
input(bintree(L, X, R), X, bintree(L, X, R)).
input(bintree(L, K, R), X, bintree(L1, K, R)) :- по-голямо(K, X),
input(L, X, L1).
input(bintree(L, K, R), X, bintree(L, K, R1)) :- по-голямо(X, K),
input(R, X, R1).
Изключване на елемент от двоично наредено дърво
Задача 4: Да се дефинира отношението delelem(T1, X, T2), което се удовлетворява, ако след
изключването на елемента Х от двоичното нареденото дърво Т1 се получава двоично
нареденото дърво Т2.
Решение:
Операцията изключване на елемент от двоично наредено дърво, често се разглежда като обратна на
операцията за включване на елемент и се дефинира по следния начин:
delelem(T1, X, T2) :- input(T2, X, T1).
За съжаление delelem работи вярно само в случая, когато елементът Х е листо, а не вътрешен
връх. В случая изключването, чрез така дефинираното отношение delelem не е определено.
За да дефинираме отношението delelem(T1, X, T2) ще използваме отношението delmin(T, Y, T1),
което е истина, ако Y е минималния елемент на двоично нареденото дърво Т, а Т1 е двоично
нареденото дърво, което се получава след изключване на Y от двоично нареденото дърво Т.
Тогава отношението delelem(Т1, Х, Т2) има вида:
delelem(bintree(nil, X, R), X, R) :- !.
delelem(bintree(L, X, nil), X, L) :- !.
delelem(bintree(L, X, R), X, bintree(L, C, R1)) :-
!, delmin(R, C, R1).
delelem(bintree(L, K, R), X, bintree(L1, K, R)) :-
по-голямо(K, X),
delelem(L, X, L1).
delelem(bintree(L, K, R), X, bintree(L, K, R1)) :-
по-голямо(X, K),
delelem(R, X, R1).
delmin(bintree(nil, Y, R), Y, R) :- !.
delmin(bintree(L, K, R), Y, bintree(L1, K, R)) :-
delmin(L, Y, L1).
