2016-08-31 7 views
0

私はこのようなサブツリーの、任意ですが、限られた量と樹木を表す:Prolog:任意の量のサブツリーでツリーの深さを計算する方法は?

tree(empty). 
tree(branch(R, Ts)) :- integer(R), isTreeList(Ts). 

isTreeList([]). 
isTreeList([T | Ts]) :- tree(T), isTreeList(Ts). 

(この表現が良いか悪いかであれば無視してください、それだけでこの質問をする目的のためだ)

This投稿は、バイナリツリーの深さを計算する方法を示しています。これまでの進捗状況:

depth(tree(empty), 0). 
depth(tree(branch(_, SubTrees), D) 
    :- < calculate somehow the depths D1, ..., Dn of the subtrees > 
    , max_list([D1, ..., Dn], MaxD) 
    , D is MaxD + 1 

D1, ..., Dnをどのようにして決定しますか?

EDITは: - まだ動作します@のmax66のソリューションSubTreesは、空のリストがある場合、これは失敗すること

depth(tree(empty), 0). 
depth(tree(branch(_, SubTrees), D) 
    :- maplist(depth, SubTrees, Depths) 
    , max_list(Depths, MaxD) 
    , D is MaxD + 1 

マインド:@CapelliCによると、以下の問題に対する1つの解決策です。

+2

ちょうど' maplist(深さ、サブツリー、深さ) ' – CapelliC

+0

@CapelliCを意味する: - maplist(深さ、サブツリー、深さ)、max_list(深さ、 MaxD)、DはMaxD + 1である。 – user3389669

+1

'max_list(Depths、MaxD)' – CapelliC

答えて

1

リストの値を計算するたびに、最大値を確認できます。

右手側は `のようになりますので、私は

depth(tree(empty), 0). 
depth([], 0). 
depth([T | L], D) :- 
    depth(T, D0), 
    depth(L, D1), 
    D is max(D0, D1). 
depth(tree(branch(_, SubTrees)), D) :- 
    depth(SubTrees, D0), 
    D is D0+1. 
関連する問題