트리가 최소 힙인지 점검하십시오.

Question

프롤로그에서 값을 리턴하는 술어를 얻으려면 어떻게해야합니까?

트리의 노드를 찾고 최소 힙이 있는지 확인해야합니다. 내가 그것을 이런 식 같은데요 - 지금까지

getnode(tree(_, node, _), node). 

내 코드는 다음과

minheap(tree(L, Node, empty)) :- 
    getnode(L, Val), 
    Node =< Val, 
    minheap(L). 
minheap(tree(empty, Node, R)) :- 
    getnode(R, Val), 
    Node =< Val, 
    minheap(R). 

getnode(tree(_,n,_) , n). 

입력 것은 사실이어야 유형 -

minheap(tree(empty,3,tree(tree(empty,8,empty),5,tree(empty,7,empty)))). 

출력이다.

Answer 1

이 문제를 해결하려면보다 단순한 유틸리티 유추 조건을 정의하는 것이 좋습니다.

예를 들어, lower/2 술어. 이 empty이거나 Tree 값이 Value 인 경우 성공한 lower(Tree,Value)입니다. 그래서 다음과 같이 구현할 수 있습니다 :

lower(empty,_). 
lower(tree(_,TreeValue,_),Value) :- 
    TreeValue >= Value. 

다음으로 우리는 술어 minheap/1을 정의합니다. empty 나무는 확실히 minheap입니다. 또한 그 아이가 낮은 모든 아이들이 minheap/1 자신을 s의 경우 나무는 그렇게하는 minheap입니다 :

minheap(empty). 
minheap(tree(Left,Value,Right)) :- 
    lower(Left,Value), 
    lower(Right,Value), 
    minheap(Left), 
    minheap(Right). 

하고 그게 다에요. empty, tree(empty,val,empty), tree(tree(..),val,empty), tree(empty,val,tree(..)) 및 tree(tree(..),val,tree(..)) :이 경우에 이후 minheap/1 조건에서 작업하면 다섯가지 경우를 처리해야 모든을하는 것보다 낫다. lower/2 헬퍼 조건자를 사용하면 두 가지 경우 (empty 및 tree/3) 만 처리하면됩니다.