Формулировка задачи

К-2012

Лабораторная работа №6. Бинарные деревья с использованием файлов и списков

Цель работы: смоделировать АТД «Бинарное дерево» с использованием списков и файлов. Использовать язык программирования логики Prolog.

Формулировка задачи

Смоделировать бинарное дерево со следующими возможными операциями:

· вставка и удаление элементов;

· вставка и удаление листов дерева;

· вставка и удаление элементов на любом уровне дерева;

· отображение дерева на экран;

· поиск элемента в дереве.

Первоначальное дерево хранить в двух вариантах: как список и как файл.

Лістинг програми:

domains

file = infile; outfile

domains

treetype = tree(integer, treetype, treetype); empty()

ttreelist = integer*

predicates

nondeterm writetree(treetype, integer,integer)

nondeterm tab(integer)

nondeterm intree(integer, treetype)

gt(integer,integer)

nondeterm addelement(integer, treetype, treetype)

nondeterm delelement(integer, treetype,treetype)

nondeterm delmin(treetype, integer, treetype)

nondeterm read_input(treetype)

nondeterm read_input_aux(treetype,treetype)

nondeterm add_list_to_tree(ttreelist, treetype,treetype)

clauses

add_list_to_tree([], Tree, Tree).

add_list_to_tree([X|Tail], Tree, NewTree):-

addelement(X,Tree,Tree1),

add_list_to_tree(Tail, Tree1,NewTree).

tab(0).

tab(X):-

write(" "),

X1 = X-1,

tab(X1).

writetree(empty, _, _).

writetree(tree(X,Left,Right), CurInd, Indent):-

CurInd2 = CurInd + Indent,

writetree(Right,CurInd2,Indent),

tab(CurInd2), write(X), nl,

writetree(Left,CurInd2,Indent).

gt(X,Y):-

X > Y.

intree(X,empty):-

write(X, " not in tree ", '\n'),!.

intree(X,tree(X,_,_)):-

write(X, " in tree ", '\n').

intree(X,tree(Root,Left,_)):-

gt(Root,X),

intree(X,Left).

intree(X,tree(Root,_,Right)):-

gt(X,Root),

intree(X,Right).

addelement(X, empty, tree(X, empty,empty)).

addelement(X, tree(X, Left, Right),tree(X, Left, Right)).

addelement(X, tree(Root, Left, Right),tree(Root, Left1, Right)):-

gt(Root, X),

addelement(X, Left, Left1).

addelement(X, tree(Root, Left, Right),tree(Root, Left, Right1)):-

gt(X, Root),

addelement(X, Right, Right1).

delelement(X, tree(X, empty, Right), Right).

delelement(X, tree(X, Left, empty), Left).

delelement(X, tree(X, Left, Right), tree(Y,Left, Right1)):-

delmin(Right, Y, Right1).

delelement(X, tree(Root, Left, Right), tree(Root,Left1, Right)):-

gt(Root,X),

delelement(X,Left,Left1).

delelement(X, tree(Root, Left, Right), tree(Root,Left, Right1)):-

gt(X, Root),

delelement(X,Right, Right1).

delmin(tree(Y, empty, Right), Y, Right).

delmin(tree(Root,Left, Right), Y, tree(Root, Left1, Right)):-

delmin(Left, Y, Left1).

read_input(InTree):-

read_input_aux(empty, InTree).

read_input_aux(Tree, NewTree):-

readint(S), nl,

addelement(S,Tree, Tree1),

read_input_aux(Tree1, NewTree).

read_input_aux(Tree, Tree).

goal

write("Please, input file name: "),

readln(InFileName), nl,

openread(infile, InFileName),

readdevice(infile),

read_input(TX),

write(TX,'\n'),

writetree(TX,0,8),

intree(6,TX),

intree(12,TX),

write("add 22 to tree", '\n'),

addelement(22, TX, T9),

writetree(T9,0,8),

write("delete 5 from tree", '\n'),

delelement(5, T9, T10),

writetree(T10,0,8),!,fail.

Результат:

Висновок: на лабораторній роботі ми навчились створювати бінарні дерева, освоїли методи реалізації операцій над ними.

Поиск по сайту: