#### 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).
```