Деревья Лекция 9. План Принадлежность значения дереву Замена в дереве всех вхождений одного значения на другое Подсчет общего количества вершин дерева. - презентация

1 Деревья Лекция 9

2 План Принадлежность значения дереву Замена в дереве всех вхождений одного значения на другое Подсчет общего количества вершин дерева Подсчет количества листьев дерева Сумма чисел, расположенных в вершинах дерева Вычисление высоты дерева Проверка принадлежности значения двоичному справочнику Добавление в двоичный справочник нового значения Алгоритм, генерирующий дерево, которое является двоичным справочником и состоит из заданного количества вершин, в которых будут размещены случайные целые числа Удаление заданного значения из двоичного справочника Преобразование произвольного списка в двоичный справочник «Сворачивание» двоичного справочника в список с сохранением порядка элементов

3 Принадлежность значения дереву DOMAINS tree=empty;tr(i,tree,tree) CLAUSES tree_member(X,tr(X,_,_)):–!. tree_member(X,tr(_,L,_)):– tree_member(X,L),!. tree_member(X,tr(_,_,R)):– tree_member(X,R).

4 Замена в дереве всех вхождений одного значения на другое tree_replace(_,_,empty,empty). tree_replace(X,Y,tr(X,L,R),tr(Y,L1,R1)):– !, tree_replace(X,Y,L,L1), tree_replace(X,Y,R,R1). tree_replace(X,Y,tr(K,L,R),tr(K,L1,R1)):– tree_replace(X,Y,L,L1), tree_replace(X,Y,R,R1).

5 Подсчет общего количества вершин дерева tree_length (empty,0). tree_length(tr(_,L,R),N):– tree_length (L,N1), tree_length (R,N2), N=N1+N2+1.

6 Подсчет количества листьев дерева tree_leaves(empty,0). tree_leaves(tr(_,empty,empty),1):–!. tree_leaves(tr(_,L,R),N):– tree_leaves(L,N1), tree_leaves(R,N2), N=N1+N2.

7 Сумма чисел, расположенных в вершинах дерева tree_sum (empty,0). tree_sum(tr(X,L,R),N):– tree_sum (L,N1), tree_sum (R,N2), N=N1+N2+X.

8 Вычисление высоты дерева tree_height(empty,0). tree_height(tr(_,L,R),D) :– tree_height(L,D1), tree_height(R,D2), max(D1,D2,D_M), D=D_M+1.

9 Проверка принадлежности значения двоичному справочнику tree_member2(X,tr(X,_,_)):–!. tree_member2(X,tr(K,L,_)):– XK,!, tree_member2(X,R).

10 Добавление в двоичный справочник нового значения tree_insert(X,empty,tr(X,empty,empty)). tree_insert(X,tr(X,L,R),tr(X,L,R)):–!. tree_insert(X,tr(K,L,R),tr(K,L1,R)):– X

11 Генерация двоичного справочника со случайными числами tree_gen(0,empty):–!. tree_gen (N,T):– random(100,X), N1= N–1, tree_gen (N1,T1), tree_insert(X,T1,T).

12 Удаление заданного значения из двоичного справочника tree_del_min(tr(X,empty,R), R, X). tree_del_min(tr(K,L,R), tr(K,L1,R), X):– tree_del_min(L, L1, X). tree_delete(X,tr(X,empty,R), R):–!. tree_delete (X,tr(X,L,empty), L):–!. tree_delete (X,tr(X,L,R), tr(Y,L,R1)):– tree_del_min(R,R1, Y). tree_delete (X,tr(K,L,R), tr(K,L1,R)):– X

13 Преобразование произвольного списка в двоичный справочник list_tree([],empty). list_tree([H|T],Tr):– list_tree(T,Tr1), tree_insert(H,Tr1,Tr).

14 «Сворачивание» двоичного справочника в список с сохранением порядка элементов tree_list(empty,[]). tree_list(tr(K,L,R),S):– tree_list(L,T_L), tree_list(R,T_R), conc(T_L,[K|T_R],S).

15 Задача для самостоятельного решения Разработать предикат, который создает справочник из количества вершин, большего максимального значения, задаваемого в random. Разработать предикат, который создает двоичный справочник, состоящий ровно из заданного количества вершин. Разработать предикат, выполняющий сортировку списка (с помощью двоичного справочника)