用PROLOG创建二叉树 [英] Creating Binary Tree in Prolog
本文介绍了用PROLOG创建二叉树的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我是PROLOG的初学者,我的第一个任务是实现一个函数Construction(),它从一个列表构建一棵二叉树。我知道我的代码中有错误或遗漏了什么,但我不能确定是什么。我也认为帮助器方法可能是必要的,但我想不出该怎么做。 到目前为止,我的代码如下:
construct([],nil).
construct(E, tree(E,nil,nil)).
construct([H|T], tree(H, construct(T,R), nil)):-
T>H.
construct([H|T], tree(H, construct(T,R), nil)):-
T<H.
推荐答案
在序言中,我们可以使用:
- 原子
nil
表示空二叉树, t(Left, Root, Right)
形式的术语,表示非空二叉树,其中Root
是树根的值,Left
和Right
也是表示二叉树的术语。
为了使二叉树更容易查看,您可以使用以下谓词:
show(T) :-
show(T, 0).
show(nil, _).
show(t(Left, Root, Right), Indent) :-
Indent1 is Indent + 3,
show(Right, Indent1),
format('~*c~w
', [Indent, 32, Root]),
show(Left, Indent1).
示例:
?- show( t(t(nil,1,nil), 2, t(nil,3,nil)) ).
3
2
1
true.
设List
是表示遍历任意二叉树的in-order的列表,如下图所示:
然后,由于不同的二叉树可以具有相同的顺序遍历,因此与该列表相对应的二叉树可以描述如下:
% convert from in-order traversal list to binary tree
list_to_bt(List, Tree) :-
( List = []
-> Tree = nil
; Tree = t(Left, Root, Right),
append(Prefix, [Root|Suffix], List),
list_to_bt(Prefix, Left),
list_to_bt(Suffix, Right) ).
示例:
?- list_to_bt([1,2,3], T), show(T).
3
2
1
T = t(nil, 1, t(nil, 2, t(nil, 3, nil))) ;
3
2
1
T = t(nil, 1, t(t(nil, 2, nil), 3, nil)) ;
3
2
1
T = t(t(nil, 1, nil), 2, t(nil, 3, nil))
...
false.
如果您只想获得平衡二叉树(例如,对于每个节点,左右子树大小的绝对差异最多为1的树),则可以按如下方式包括此约束:
% convert from in-order traversal list to balanced binary tree (bbt)
list_to_bbt(List, Tree) :-
( List = []
-> Tree = nil
; Tree = t(Left, Root, Right),
append(Prefix, [Root|Suffix], List),
length(Prefix, Size1),
length(Suffix, Size2),
abs(Size1 - Size2) =< 1,
list_to_bbt(Prefix, Left),
list_to_bbt(Suffix, Right) ).
示例:
?- list_to_bbt([1,2,3], T), show(T).
3
2
1
T = t(t(nil, 1, nil), 2, t(nil, 3, nil)) ;
false.
如果您只需要任意列表中的平衡二叉树,则必须在创建平衡二叉树之前对该列表进行排序:
% convert from arbitrary list to balanced binary search tree (bbst)
list_to_bbst(List, Tree) :-
sort(List, Sorted),
list_to_bbt(Sorted, Tree).
示例:
?- list_to_bbst([3,1,7,5,4,2,6], T), show(T).
7
6
5
4
3
2
1
T = t(t(t(nil, 1, nil), 2, t(nil, 3, nil)), 4, t(t(nil, 5, nil), 6, t(nil, 7, nil))) ;
false.
?- list_to_bbst([3,1,4,2], T), show(T).
4
3
2
1
T = t(t(nil, 1, nil), 2, t(nil, 3, t(nil, 4, nil))) ;
4
3
2
1
T = t(t(nil, 1, nil), 2, t(t(nil, 3, nil), 4, nil)) ;
4
3
2
1
T = t(t(nil, 1, t(nil, 2, nil)), 3, t(nil, 4, nil)) ;
4
3
2
1
T = t(t(t(nil, 1, nil), 2, nil), 3, t(nil, 4, nil)) ;
false.
这篇关于用PROLOG创建二叉树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文