0

我想找到二叉树的最深元素，到目前为止，代码仅适用于空树或高度为一。

这是我的高度功能正常工作的代码。

deepest(node(L,X,R),X):- height(L,0),height(R,0).
deepest(node(L,_,R),X):- height(L,D1),height(R,D2), D1 > D2,  deepest(L,X).
deepest(node(L,_,R),X):- height(L,D1),height(R,D2), D1 =< D2, deepest(R,X).

编辑：示例

?- deepest(node(node(node(leaf,8,leaf),20,leaf),
                      30,
                      node(node(leaf,88,leaf),33,node(leaf,888,leaf))),
                 X).
X = 8 ;
X = 88 ;
X = 888 ;
false.
4

2 回答 2

1

我怀疑这种关系height（顺便说一句，Prolog 中没有函数）对任务没有用，因为它忘记了所需的基本信息。

deepest(T, E) :-
    deepest(T, E, _).

deepest(node(L, X, R), E, D) :-
    deepest(L, EL, DL),
    deepest(R, ER, DR),
    (   DL > DR
    ->  E = EL, D is DL + 1
    ;   (   DL < DR
        ->  E = ER, D is DR + 1
        ;   (   DL > 0  % DL & DR are equals
            ->  E = L, D is DL % deepest is arbitrary here
            ;   E = X, D is 1
            )
        )
    ).
deepest(N, N, 0).

编辑预期的数据结构，而不是deepest(N, N, 0).我认为使用起来更清晰

deepest(_, _, 0).
于 2012-10-12T06:33:51.310 回答
0

这是一个替代版本，它使用了一些基本的内置插件，即append/3、keysort/2、reverse/2和maplist/3：

deepest(Tree, N) :-
    deepest(Tree, 0, NL),
    maplist(strip_key, NL, N).

deepest(leaf, _, []). 
deepest(node(L, X, R), D, [DN-N|Res]) :-
    NewD is D + 1,
    deepest(L, NewD, LL), 
    deepest(R, NewD, RL),
    append([D-X|LL], RL, NL),
    keysort(NL, KL),
    reverse(KL, [DN-N|Rem]),
    first_key_run(Rem, DN, Res).

first_key_run([DN-N|Rem], DN, [DN-N|NL]) :-
    !, 
    first_key_run(Rem, DN, NL).
first_key_run(_, _, []).

strip_key(_K-V, V).

Depth-Node这个版本在树的每个节点上建立一个项目列表，执行keysort/2最浅优先的列表（O（N·log（N）），颠倒顺序（O（N）），然后保留第一个运行相同深度的节点 (O(N))。

此版本还精确计算等深深度处的节点数。例如：

?- deepest(node(node(node(leaf,8,leaf),20,leaf),30,node(node(leaf,88,leaf),33,node(leaf,888,leaf))), X).
X = [88, 888, 8].
于 2012-10-14T06:08:38.990 回答