recursion - 给定 Prolog 中的元素列表，创建所有可能的 AVL 树

Question

给定一个元素列表，返回所有可能包含该列表元素的平衡二叉树。在我们的例子中，一个有效的树是这样的结构：tree(_, left, right). 例如：

?- avl_tree_planter(X, [yin, yang]).
X = tree(yang, tree(yin, nil, nil), nil) ;
X = tree(yin, tree(yang, nil, nil), nil) ;
X = tree(yin, nil, tree(yang, nil, nil)) ;
X = tree(yang, nil, tree(yin, nil, nil)) ;

我尝试使用中序、前序和后序遍历输出所有可能的选项：

abs_diff(L,R,D) :- D is L-R, L >= R.
abs_diff(L,R,D) :- D is R-L, R >= L.

height(nil,0).
height(tree(_,L,R), H) :- 
    height(L,HL), height(R,HR), 
    max_num(HL,HR,MaxH), H is MaxH + 1.

avl_tree_planter(nil,[]).
avl_tree_planter(tree(X,L,R), Xs) :-
    height(L,HL), height(R,HR),
    abs_diff(HL,HR,Diff), Diff =< 1, 
    avl_tree_planter(L,Ls), avl_tree_planter(R,Rs), 
    append(Ls,[X|Rs],Xs).     % inorder
avl_tree_planter(tree(X,L,R), Xs) :-  
    height(L,HL), height(R,HR),
    abs_diff(HL,HR,Diff), Diff =< 1,
    avl_tree_planter(L,Ls), avl_tree_planter(R,Rs), 
    append(Rs, [X], Xs1),     % postorder
    append(Ls, Xs1, Xs).  
avl_tree_planter(tree(X,L,R), Xs) :-  
    height(L,HL), height(R,HR),
    abs_diff(HL,HR,Diff), Diff =< 1,
    avl_tree_planter(L,Ls), avl_tree_planter(R,Rs), 
    append([X|Ls], Rs, Xs).   % preorder

在输入的一些在线解释器中：

avl_tree_planter(X,[a,b]).

它输出：

X = tree(a, nil, tree(b, nil, nil))

十二次，然后进入无限循环，再一次无限循环。

我已经为递归设置了停止条件，所以我做错了什么？

标签： recursiontreeprologbinary-treeavl-tree

Answer 1

这在无限循环中得到stuc的原因是因为您height/2使用生成和测试方法：它首先构造一棵树，然后验证高度是否与所需高度匹配。但是随着树越来越大，最终您的检查将开始拒绝这些树，但是没有办法告诉您的谓词停止提议新树。

我们可以构建每个节点最多相差一个的 AVL 树，如下所示：

:- use_module(library(clpfd)).

height(nil, 0).
height(tree(_, L, R), H) :-
    H #> 0,
    H1 #= H-1,
    H2 #= H-2,
    (
        (height(L, H1), height(R, H1));
        (height(L, H1), height(R, H2));
        (height(L, H2), height(R, H1))
    ).

现在我们可以生成树，并用额外的元素“标记”这些树的节点。height/3制作一个导出变量列表的更通用的谓词可能会有所帮助：

height(T, H, N) :-
    height(T, H, N, []).

height(nil, 0, N, N).
height(tree(X, L, R), H, [X|Ni], No) :-
    H #> 0,
    H1 #= H-1,
    H2 #= H-2,
    (
        (height(L, H1, Ni, Nt), height(R, H1, Nt, No));
        (height(L, H1, Ni, Nt), height(R, H2, Nt, No));
        (height(L, H2, Ni, Nt), height(R, H1, Nt, No))
    ).

例如：

?- height(T, 2, N).
T = tree(_622, tree(_642, nil, nil), tree(_662, nil, nil)),
N = [_622, _642, _662] ;
T = tree(_622, tree(_642, nil, nil), nil),
N = [_622, _642] ;
T = tree(_622, nil, tree(_642, nil, nil)),
N = [_622, _642] ;
false.

我把它留作练习，用列表中的元素标记树。