序言：構建一棵完全平衡的樹

Question

有沒有人知道在Prolog中構建完全平衡樹的簡單方法？

下面是我找到的一種解決方案，但我想知道是否有人知道任何更簡單的解決方案？

這個很簡單，但花了我一點時間來準確掌握它的工作原理。

謝謝:)。

% from given solution 

cbal_tree(0, nil) :- !. 
cbal_tree(N, t(x,L,R)) :- 
    N > 0, 

    N0 is N - 1, % if N is 4, this would be 3 

    N1 is N0 mod 2, % if N is 4, this would be 3 mod 2 = 1 
    N2 is N0 - N1, % if N is 4, this would be 3-1= 2 

    distrib(N1, N2, LeftNode, RightNode), 

    cbal_tree(LeftNode, L), 
    cbal_tree(RightNode, R). 

distrib(N,N,N,N) :- !. 
distrib(N1,N2,N1,N2). % giving these two clauses (*) 1,2,?,? could give 1,2 or 2,1 
distrib(N1,N2,N2,N1). % (*) 

Answer 1

這個構建對稱樹：

symm_tree(nil,0). 
symm_tree(t(L,R),Level) :- 
    Level > 0, 
    M is Level-1, 
    symm_tree(L,M), 
    symm_tree(R,M). 

添加標籤的節點應該是微不足道的。

您發佈的代碼可以稍微簡化爲

cbal_tree(0, nil). 
cbal_tree(N, t(x,L,R)) :- 
    N > 0, 
    N0 is N - 1, % -1 to account for root node 
    N1 is N0 mod 2, 
    N2 is N0 - N1, 

    permutation([N1,N2], [NLeft,NRight]), 

    cbal_tree(NLeft, L), 
    cbal_tree(NRight, R). 

但這的確是多麼簡單獲取和處理distrib/3重複的走了。