用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.