Ternary Trees

Inspired by an article in Dr. Dobb's Journal, April 1998.

  check_determ
domains
  chars = char*
  tree  = tree(char,tree,tree,tree) ; void
predicates
  insert(chars,tree,tree)
  search(chars,tree)
  traverse(tree)
  traverse_1(tree,string)
  traverse_2(char,tree,string)
clauses

/* insert(Characters, Tree0, Tree) is true if Tree is the result of        */
/*   inserting the Characters in the ternary search tree Tree0.            */
insert([], void, tree('\0',void,void,void)).
insert([], tree('\0',Lo,Eq,Hi), tree('\0',Lo,Eq,Hi)):-!.
insert([X|Xs], void, tree(X,void,Eq,void)):-
  insert(Xs, void, Eq).
insert([X|Xs], tree(C,Lo,Eq,Hi), tree(C,Lo,Eq,Hi1)):-
  X > C, !,
  insert([X|Xs], Hi, Hi1).
insert([X|Xs], tree(X,Lo,Eq,Hi), tree(X,Lo,Eq1,Hi)):-
  !, insert(Xs, Eq, Eq1).
insert(Xs, tree(C,Lo,Eq,Hi), tree(C,Lo1,Eq,Hi)):-
  insert(Xs, Lo, Lo1).
 
/* search(Characters, Tree) is true if the Characters are contained in     */
/*   the ternary search tree Tree.                                         */
search([], tree('\0',_,_,_)):-!.
search([X|Xs], tree(C,_,_,Hi)):-
  X > C, !,
  search([X|Xs], Hi).
search([X|Xs], tree(X,_,Eq,_)):-
  !, search(Xs, Eq).
search(Xs, tree(_,Lo,_,_)):-
  search(Xs, Lo).
 
/* traverse(Tree) traverses the ternary search tree Tree, and displays the */
/*   strings in the tree in sorted order.                                  */
traverse(Tree):-traverse_1(Tree, "").
 
traverse_1(void, _).
traverse_1(tree(C,Lo,Eq,Hi), String):-
  traverse_1(Lo, String),
  traverse_2(C, Eq, String),
  traverse_1(Hi, String).
 
traverse_2('\0', void, String):-
  !,
  write(String), nl.
traverse_2(C, Tree, String):-
  str_char(String1, C),
  concat(String, String1, String2),
  traverse_1(Tree, String2).

Turbo Prolog Index     Home Page