| 1 | #!/usr/bin/env swipl -s
|
|---|
| 2 |
|
|---|
| 3 | /*
|
|---|
| 4 | * Rick van der Zwet
|
|---|
| 5 | * 0433373
|
|---|
| 6 | * Prolog programming assigment 2
|
|---|
| 7 | * Licence: BSD
|
|---|
| 8 | * $Id: assignment2.pro 299 2007-11-08 00:10:31Z rick $
|
|---|
| 9 | *
|
|---|
| 10 | * We shall consider binary trees whose nodes are (labelled with)
|
|---|
| 11 | * natural numbers, and use the term void to denote the empty tree, and
|
|---|
| 12 | * the term tree(x, left, right). to denote the tree with root x, left
|
|---|
| 13 | * subtree left and right subtree right. For example, the term tree(1,
|
|---|
| 14 | * tree(2, void, void), tree(3, void, void)) represents the tree with
|
|---|
| 15 | * root 1 and children 2 and 3
|
|---|
| 16 | * We call a binary tree tree(x, left, right) nice if:
|
|---|
| 17 | * 1. if left is not empty then x is greater than all the elements in
|
|---|
| 18 | * left
|
|---|
| 19 | * 2. if right is not empty then x is less than all the elements in
|
|---|
| 20 | * right.
|
|---|
| 21 | *
|
|---|
| 22 | * A binary tree is called a search tree if every subtree of it is nice.
|
|---|
| 23 | * Write a program which tests whether a ground term is a search tree.
|
|---|
| 24 | *
|
|---|
| 25 | * Hint: Use the following predicate is_search_tree(T) in the definition
|
|---|
| 26 | * of search tree:
|
|---|
| 27 | * is_search_tree(void).
|
|---|
| 28 | * is_search_tree(T) :- is_search_tree(T, Min, Max).
|
|---|
| 29 | * where Min and Max are the minimum and maximum element of the tree T.
|
|---|
| 30 | * Then implement the predicate is_search_tree(T, Min, Max).
|
|---|
| 31 | */
|
|---|
| 32 |
|
|---|
| 33 |
|
|---|
| 34 | /* Make a call to a void/2 fail to make the once(call( fail when calling
|
|---|
| 35 | * the void X X
|
|---|
| 36 | */
|
|---|
| 37 | void(_, _) :-
|
|---|
| 38 | fail.
|
|---|
| 39 |
|
|---|
| 40 | /* Calculate wether leaf is valid */
|
|---|
| 41 | tree(X, void, void, Min, Max) :-
|
|---|
| 42 | X =< Max,
|
|---|
| 43 | X >= Min.
|
|---|
| 44 |
|
|---|
| 45 | /* Only Left set, make the call */
|
|---|
| 46 | tree(X, Left, void, Min, _) :-
|
|---|
| 47 | once(call(Left, Min, X)).
|
|---|
| 48 |
|
|---|
| 49 | /* Only Right set, make the call */
|
|---|
| 50 | tree(X, void, Right, _, Max) :-
|
|---|
| 51 | once(call(Right, X, Max)).
|
|---|
| 52 |
|
|---|
| 53 | /* Both set, make the call */
|
|---|
| 54 | tree(X, Left, Right, Min, Max) :-
|
|---|
| 55 | once(call(Left, Min, X)),
|
|---|
| 56 | once(call(Right, X, Max)).
|
|---|
| 57 |
|
|---|
| 58 | /* Initial values */
|
|---|
| 59 | tree(X, Left, Right) :-
|
|---|
| 60 | tree(X, Left, Right, -32768, 32768).
|
|---|
| 61 |
|
|---|
| 62 | /* Exception single tree node */
|
|---|
| 63 | tree(_, void, void) :-
|
|---|
| 64 | true.
|
|---|
| 65 |
|
|---|
| 66 | /* Exception no node */
|
|---|
| 67 | is_search_tree(void).
|
|---|
| 68 |
|
|---|
| 69 | is_search_tree(T) :-
|
|---|
| 70 | once(call(T)).
|
|---|
