给定 Prolog 中的元素列表,创建所有可能的 AVL 树
Create all possible AVL trees given a list of elements in Prolog
给定一个元素列表,return 所有可能的平衡二叉树恰好包含该列表的元素。在我们的例子中,有效树的构造是: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))
12次然后进入无限循环,再一次无限循环。
我已经为递归设置了停止条件,所以我做错了什么?
这在无限循环中得到 stuc 的原因是因为您的 height/2
使用 generate-and-test 方法:它首先构造一棵树,然后它验证高度是否符合要求的高度。但是随着树越来越大,最终你的检查将开始拒绝这些树,但是没有办法告诉你的谓词停止提议新树。
我们可以构建每个节点最多相差1的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))
).
现在我们可以生成树,并且"tag"这些树的节点带有额外的元素。它可能有助于制作一个更通用的谓词 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.
我把它留作练习,用列表中的元素标记树。
给定一个元素列表,return 所有可能的平衡二叉树恰好包含该列表的元素。在我们的例子中,有效树的构造是: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))
12次然后进入无限循环,再一次无限循环。
我已经为递归设置了停止条件,所以我做错了什么?
这在无限循环中得到 stuc 的原因是因为您的 height/2
使用 generate-and-test 方法:它首先构造一棵树,然后它验证高度是否符合要求的高度。但是随着树越来越大,最终你的检查将开始拒绝这些树,但是没有办法告诉你的谓词停止提议新树。
我们可以构建每个节点最多相差1的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))
).
现在我们可以生成树,并且"tag"这些树的节点带有额外的元素。它可能有助于制作一个更通用的谓词 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.
我把它留作练习,用列表中的元素标记树。