Geek Answers Handbook

Prolog, restores BST trees from the list of orders

We well know the inorder implementation for the BST tree.

 inorder(nil, []). inorder(t(Root, L, R), List) :- inorder(L, ListLeft), inorder(R, ListRight), append(ListLeft, [Root|ListRight], List).

However, is it possible to do this for a list? I mean restoring all possible BST trees, for example:

 inorder(X, [1,2,3]). X = t(1, nil, t(2, nil, t(3, nil, nil)))); X = t(3, t(2, t(1, nil, nil), nil), nil), nil); X = t(2, t(1, nil, nil), t(3, nil, nil)); false.

It seems impossible to me.

+5
source share
2 answers

First, let's use the Specific Phrase ( dcg ) grammar to bind trees to lists:

  inorder (nil) -> [].
 inorder (t (Root, L, R)) ->
     inorder (L),
     [Root],
     inorder (R).

The trick I just applied is described in Ulrich Neumerkel's dissertation in the section "Taming the Left Recursion".

"... we add another state for the number of tokens that can be used by newly encountered non-terminals. Therefore, the number of tokens that will be considered by terminals within the same rule is reserved in advance.

In our case:

  inorder (nil, Es , Es ) -> [].
 inorder (t (Root, L, R), [_ | Es0] , Es ) ->
     inorder (L, Es0 , Es1 ),
     [Root],
     inorder (R, Es1 , Es ).

Request example ( Ls omitted):

  ? - Ls = [1,2,3], phrase (inorder (Tree, Ls, _), Ls).
 Tree = t (1, nil, t (2, nil, t (3, nil, nil)));
 Tree = t (1, nil, t (3, t (2, nil, nil), nil));
 Tree = t (2, t (1, nil, nil), t (3, nil, nil));
 Tree = t (3, t (1, nil, t (2, nil, nil)), nil);
 Tree = t (3, t (2, t (1, nil, nil), nil), nil);
 false

Another way to solve such problems is to use the tab run mechanism.

+4
source

If you like the trick I suggested here , the only change required could be

<Preview>: - use_module (carlo ( fragments / when_ )).
 inorder(t(Root, L, R), List) -:- ...

and now

 ?- inorder(T,[1,2,3]). T = t(1, nil, t(2, nil, t(3, nil, nil))) ; T = t(1, nil, t(3, t(2, nil, nil), nil)) ; T = t(2, t(1, nil, nil), t(3, nil, nil)) ; T = t(3, t(1, nil, t(2, nil, nil)), nil) ; T = t(3, t(2, t(1, nil, nil), nil), nil) ; false.
+1
source

More articles:


All Articles