バイナリツリーの同じレベルのノードの最大数（プロローグ）

Question

ノードのセットとして二分木構造を定義でき、ツリー自体は検索：

• 空であるか、または、
• そこで我々は次のbinaryTree述語を満たす用語のセットとPrologでバイナリツリーを表すことができ、上述の定義に中継するルートノードと左右バイナリサブツリーノード

から成ります。例えば

binaryTree(nil):- !. 
binaryTree(bTree(L, _, R)):- binaryTree(L), binaryTree(R). 

、以下のB木

は構造に対応：

bTree(bTree(nil, b, nil), a, bTree(bTree(nil, d, nil), c, nil)) 

私の質問は、与えられたバイナリツリーの長さの求め方についてです、すなわち同じレベルのノードの最大数。あなたはこのような何かを行うことができ

Answer 1

は（それはあなた次第です、正確性を検証するために多くのテストを行っていない）：

binaryTree(nil):- !. 
binaryTree(bTree(L, _, R)):- binaryTree(L), binaryTree(R). 

max_length(T, Max):- 
    traverse(T, 0, Ts), 
    get_levels(Ts, Levels), 
    sort(0, @=<, Levels, Levels1), 
    get_max_length(Levels1, _, 0, 0, Max). 

traverse(bTree(L,V,R), Level, bTree(L1, V, R1, Level)):- 
    Level1 is Level + 1, 
    traverse(L, Level1, L1), 
    traverse(R, Level1, R1). 

traverse(nil, _, nil). 

get_levels(nil, []). 

get_levels(bTree(L,_,R, Lev), [Lev|Levs2]):- 
    get_levels(L, Levs0), 
    get_levels(R, Levs1), 
    append(Levs0,Levs1,Levs2). 

get_max_length([], _, Acc,Max0, Max1):- 
    (Acc > Max0 -> 
    Max1 is Acc;  
    Max1 is Max0 
    ). 

get_max_length([Curr|T], Curr, Acc, Max0, Max1):- 
    Acc1 is Acc + 1, 
    get_max_length(T, Curr, Acc1, Max0, Max1). 

get_max_length([X|T], Curr, Acc, Max0, Max1):- 
    \+ X = Curr, 
    (Acc > Max0 -> 
    get_max_length(T, X, 1, Acc, Max1);  
    get_max_length(T, X, 1, Max0, Max1) 
    ). 

2テストケース、あなたの写真の最初のツリーと、この木を：

            +-----+ 
                -+-----+--- 
               ---/   \----- 
            +------+--/      \+------+ 
           --+------+       ++-----+--- 
           -/   |       |   \--- 
         +-----+/   +------+   +-------/    \+------+ 
         /-----\   /------\   /-------\    +/-----+- 
        -/  \   -/  \  -/   \-   -/  \--- 
        -/   |  -/   |  -/    \   -/    \-- 
      +-----/  +------\ +/----+ +----\ +/----+ +------\  /------+  +-----\- 
      +-----+  +------+ +-----+ +----+ +-----+ +------+  +------+  +-----+ 

詳細な回答に感謝をコードに次の行を追加し、test.

test:- 
    T0 = bTree(bTree(nil, b, nil), a, bTree(bTree(nil, d, nil), c, nil)), 
    max_length(T0, 2), 
    T1 = bTree(
       bTree(
        bTree(
          bTree(
           nil, 
           3, 
           nil 
           ), 
          2, 
          bTree(
           nil, 
           4, 
           nil 
           ) 
         ), 
        1, 
        bTree(
          bTree(
           nil, 
           6, 
           nil 
           ), 
          5, 
          bTree(
           nil, 
           7, 
           nil 
           ) 
         ) 
        ), 
       0, 
       bTree(
        bTree(
          bTree(
           nil, 
           10, 
           nil 
           ), 
          9, 
          bTree(
           nil, 
           11, 
           nil 
           ) 
         ), 
        8, 
        bTree(
          bTree(
           nil, 
           13, 
           nil 
           ), 
          12, 
          bTree(
           nil, 
           14, 
           nil 
           ) 
         ) 
        )), 
    max_length(T1, 8).