计算二叉树序言中的出现次数

Question

我想实现一个代码来获取整个树中某个数字的出现次数，例如：

numberOfOccurrences(7, bt(6, bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                             bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil))), N).
N = 1;

我该怎么做？

Answer 1

你试过定义

numberOfOccurrences(7, bt(6, bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                             bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil))), 1).

？你试过定义

numberOfOccurrences(7, bt(6, bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                             bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil))), N) :- 
                   N = 1.

？你试过定义

numberOfOccurrences(7, T, N) :-
                   T = bt(6, bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                             bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil))),
                   N = 1.

？或者甚至

numberOfOccurrences(7, T, N) :-
                   T = bt(6, TL, TR), 
                   TL =      bt(2, bt(1, nil, nil),    %%
                                   bt(3, nil, nil)),
                   TR =      bt(8, bt(7, nil, nil),    %%
                                   bt(9, nil, nil)),
                   N = 1.

？您是否也尝试过定义

numberOfOccurrences(7, T, N) :-
                   T = bt(6, TL, TR), 
                   N1 = 0,                             %%
                   TL =      bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                   NL = 0,                             %%
                   TR =      bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil)),
                   NR = 1,                             %%
                   N is N1 + NL + NR.                  %%

？

不也是这样吗

numberOfOccurrences(7, T, N) :-
                   T = bt(6, TL, TR), 
                   N1 = 0,
                   TL =      bt(2, bt(1, nil, nil),
                                   bt(3, nil, nil)),
                   numberOfOccurrences(7, TL, NL),     %%
                   NL = 0,
                   TR =      bt(8, bt(7, nil, nil),
                                   bt(9, nil, nil)),
                   numberOfOccurrences(7, TR, NR),     %%
                   NR = 1,
                   N is N1 + NL + NR.

？而且还只是

numberOfOccurrences(7, T, N) :-
                   T = bt(6, TL, TR), 
                   N1 = 0,
                                                       %%
                   numberOfOccurrences(7, TL, NL),
                                                       %%
                   numberOfOccurrences(7, TR, NR),
                                                       %%
                   N is N1 + NL + NR.

？您是否尝试过进一步概括它，删除最后的人为具体值，也用逻辑变量替换它们，

numberOfOccurrences( X, T, N) :-                       %%
                   T = bt( Y, TL, TR),                 %%
                   count_one_possible_occurrence( X, Y, N1),
                   numberOfOccurrences( X, TL, NL),    %%
                   numberOfOccurrences( X, TR, NR),    %%
                   N is N1 + NL + NR.

？你能继续这个思路吗？

Answer 2

你应该试着把大问题分解成多个小问题。所以首先：对树进行操作很复杂，列表更容易处理：

treeToList(Tree, List) :-
    % I use an accumulator, starting with an empty list.
    treeToList(Tree, [], List).

% The bottom is reached: The accumulated elements are the result.
treeToList(nil, Accu, Accu).

treeToList(bt(E, Left, Right), Accu0, List) :-
    Accu1 = [E|Accu0],              % prepend the accumulator with the current element
    treeToList(Left, Accu1, Accu2), % prepend elements of the left node
    treeToList(Right, Accu2, List). % prepend elements of the right node

?- treeToList(bt(6, bt(2, bt(1, nil, nil),
                          bt(3, nil, nil)),
                    bt(8, bt(7, nil, nil),
                          bt(9, nil, nil))), L).
L = [9, 7, 8, 3, 1, 2, 6].

在排序列表中计数比在未排序列表中计数要容易得多。 Prolog 有一个 built-in sort/2 谓词。

?- sort([9, 7, 8, 3, 1, 2, 6], L).
L = [1, 2, 3, 6, 7, 8, 9].

您可以计算相邻值的个数，一步得到剩余的不同值：

removeFromFrontAndCount(_, [], [], N, N).

removeFromFrontAndCount(E, [F|Out], [F|Out], N, N) :-
    E \= F.

removeFromFrontAndCount(E, [E|In], Out, N0, N2) :-
    N1 is N0 + 1,
    removeFromFrontAndCount(E, In, Out, N1, N2).

?- removeFromFrontAndCount(1, [1,1,1,2,3,4], L, 0, N).
L = [2, 3, 4],
N = 3 ;
false.

使用那个助手是谓词 countAdjacent/3:

countAdjacent(List0, E, N) :-
    [E0|List1] = List0,
    removeFromFrontAndCount(E0, List1, List2, 1, CountE),
    (   % a semicolon is an either-or operator
        E = E0, N = CountE;
        countAdjacent(List2, E, N)
    ).

?- countAdjacent([1,1,1,2,2,3], E, N).
E = 1, N = 3 ;
E = 2, N = 2 ;
E = 3, N = 1 ;
false.

并结合一切：

numberOfOccurrences(E, Tree, N) :-
    treeToList(Tree, List),
    sort(List, SortedList),
    countAdjacent(SortedList, E, N).

?- numberOfOccurrences(E, bt(6, bt(2, bt(1, nil, nil),
                                bt(3, nil, nil)),
                          bt(8, bt(7, nil, nil),
                                bt(9, nil, nil))), L).
E = 1, L = 1 ;
E = 2, L = 1 ;
E = 3, L = 1 ;
E = 6, L = 1 ;
E = 7, L = 1 ;
E = 8, L = 1 ;
E = 9, L = 1 ;
false.

完整代码：

numberOfOccurrences(E, Tree, N) :-
    treeToList(Tree, List),
    sort(List, SortedList),
    countAdjacent(SortedList, E, N).


treeToList(Tree, List) :-
    treeToList(Tree, [], List).

treeToList(nil, Accu, Accu).

treeToList(bt(E, Left, Right), Accu0, List) :-
    treeToList(Left, [E|Accu0], Accu1),
    treeToList(Right, Accu1, List).


countAdjacent(List0, E, N) :-
    [E0|List1] = List0,
    removeFromFrontAndCount(E0, List1, List2, 1, CountE),
    (
        E = E0, N = CountE;
        countAdjacent(List2, E, N)
    ).


removeFromFrontAndCount(_, [], [], N, N).

removeFromFrontAndCount(E, [F|Out], [F|Out], N, N) :-
    E \= F.

removeFromFrontAndCount(E, [E|In], Out, N0, N2) :-
    N1 is N0 + 1,
    removeFromFrontAndCount(E, In, Out, N1, N2).

计算二叉树序言中的出现次数

Counting occurrences in binary tree prolog

binary-tree

prolog