Prolog，从中序列表重建BST树 [英] Prolog, reconstruct BST trees from inorder list

问题描述

我们很清楚 BST 树的 inorder 实现.

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

但是，可以为 list 做吗?我的意思是重建所有可能的 BST 树，例如:

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));错误的.

这对我来说似乎是不可能的.

解决方案

首先，让我们使用定语从句语法(dcg) 用于将树与列表相关联:

<预>中序(无)--> [].中序(t(Root, L, R)) -->中序(L),[根]，中序(R).

我现在要应用的技巧在 Ulrich Neumerkel 的 论文驯服左递归.

<块引用>

...我们为新遇到的非终结符可以使用的令牌数量添加另一个状态.因此，预先保留单个规则内终端将读取的令牌数量."

在我们的例子中:

<预>inorder(nil, Es, Es) --> [].中序(t(Root, L, R), [_|Es0], Es) -->中序(L, Es0, Es1),[根]，中序(R，Es1，Es).

示例查询(省略了Ls):

<预>?- Ls = [1,2,3], 短语(inorder(Tree, Ls, _), Ls).树 = t(1, nil, t(2, nil, t(3, nil, nil))) ;树 = t(1, nil, t(3, t(2, nil, nil), nil)) ;树 = t(2, t(1, nil, nil), t(3, nil, nil)) ;树 = t(3, t(1, nil, t(2, nil, nil)), nil) ;树 = t(3, t(2, t(1, nil, nil), nil), nil) ;错误的.

解决此类问题的另一种方法是使用 Prolog 系统的表格机制.

We well know inorder implementation for 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 it for list ? I mean reconstruct 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 to be impossible for me.

解决方案

First, let us use a Definite Clause Grammar (dcg) for relating trees to lists:

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

The trick I will now apply is described in Ulrich Neumerkel's dissertation in Taming Left Recursion.

"... we add another state for the number of tokens that can be used by newly encountered nonterminals. The number of tokens that will be read by the terminals within a single rule are therefore 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).

Sample query (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 issues is to use your Prolog system's tabling mechanism.

这篇关于Prolog，从中序列表重建BST树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！