0

バイナリ ツリーの最も深い要素を見つけたいのですが、これまでのところ、コードは空のツリーまたは高さが 1 の場合にのみ機能します。

これが私の高さ関数が正しく機能するコードです。

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 に答える