%
% tree.prolog
%
% Developed by Ondrej Jombik <nepto@platon.sk>
% Copyright (c) 2005 Platon SDG, http://platon.sk/
% Licensed under terms of GNU General Public License.
% All rights reserved.
%
% Changelog:
% 2005-05-02 - created
%

% $Platon: scripts/prolog/tree.prolog,v 1.1 2005/05/02 10:55:41 nepto Exp $

%
% binary tree
%

bt(node(_,nil,nil)).
bt(node(_,Left,Right)):-bt(Left),bt(Right).

%
% binary search tree
%

lt(_,nil).
lt(X,node(Value,nil,nil)):-Value=<X.
lt(X,node(Value,Left,Right)):-Value=<X,lt(X,Left),lt(X,Right).

gt(_,nil).
gt(X,node(Value,nil,nil)):-Value>=X.
gt(X,node(Value,Left,Right)):-Value>=X,gt(X,Left),gt(X,Right).

bt_search(nil).
bt_search(node(Value,Left,Right)):-bt_search(Left),bt_search(Right),lt(Value,Left),gt(Value,Right).