用PROLOG创建二叉树 [英] Creating Binary Tree in 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屋！