2

Доброго времени суток, помогите пожалуйста с доработкой программы.

Задача заключается в поиске уровня максимального элемента в дереве (ниже приведён код рабочей программы). Проблема в том, что по коду мы проходим дерево два раза в поиске максимального элемента (max_n) и в поиске уровня того же элемента (find_tree).

Необходимо как-то запомнить уровень элемента уже в поиске максимального.

domains
treetype = tree(integer, treetype, treetype); empty
predicates
max_n(treetype, integer)
max(integer,integer,integer)
find_tree(treetype,integer,integer)

clauses

max(M,N,N) :- N>=M, !.
max(M,N,M) :- M>=N, !.
max_n(tree(X,empty,empty),X) :- !.
max_n(tree(X,empty,R),Q) :- max_n(R,N), max(X,N,Q).
max_n(tree(X,L,empty),Q) :- max_n(L,N), max(X,N,Q).
max_n(tree(X,L,R),Q) :- max_n(L,LM), max_n(R,RM), max(RM,LM,QM), max(X,QM,Q). 

find_tree(tree(N,_,_),N,0):-!.
find_tree(tree(_,L,_),X,K):-
  find_tree(L,X,K1),
  K=1+K1.
find_tree(tree(_,_,R),X,K):-
  find_tree(R,X,K1),
  K=1+K1.  

goal
T=tree(3,tree(4,tree(5,empty,tree(6,empty,tree(1,empty,empty))),tree(7,empty,empty)),tree(8,empty,empty)),  
max_n(T,M),
write("Max:", M),nl,
find_tree(T,M,K), write(M, " na ",K," urovne"),nl.
ixSci
  • 23,825
catechumen
  • 21

1 Answers1

0

Необходимо как-то запомнить уровень элемента уже в поиске максимального.

Вы можете записывать факты базы данных level/2 для этой цели:

 database
    level ( integer, integer ) /* tree_node_ID, level */

 predicate
    cleanup_level_info. 
    record_level( integer, integer ).
    recorded( integer, integer ).

Можно вообще отказаться от "древесного" представления деревьев и использовать отношения базы данных ( в данном случае, внутренней ).

Отношения базы данных ( факты ) не должны иметь несвязанных переменных и должны быть плоскими (без списков и составных термов ).

Например, дерево из раздела goal могло бы выглядеть так:

 database
    tree( integer, integer, integer ) 

    /* -1 = empty */    
    tree( 3, 4, 8 ).
    tree( 4, 5, 7 ).
    tree( 5, -1, 6 ).
    tree( 6, -1, 1 ).
    tree( 1, -1, -1 ).
    tree( 7, -1, -1 ).
    tree( 8, -1, -1 ).
Anton Danilov
  • 601