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