Prologでバイナリツリー要素をリストにソートしますか？

Question

私は2つのツリーを3つのリストにソートしようとしています.1つは正数、1つは負数、もう1つは他のものです。

私が正常にリストにツリーを変換し、このコードを持っている：

treePosNeg(void, []). 
treePosNeg(tree(Left,Root,Right),[Root|List]) :- 
    treePosNeg(Left,List1), 
    treePosNeg(Right,List2), 
    append(List1,List2,List). 

入力：

treePosNeg(tree(tree(void,a,void),-10,tree(void,b,void)),List). 

出力：それらをソートする

List = [-10, a, b] 

私の論理は単純でしたRoot> = 0、Root <が0かどうかをチェックし、そうでない場合は他のリストに入ります。私はtreePosNegの3つの述語を使用して、それぞれの特定の型をチェックしようとしていました。

treePosNeg(void, []). 
treePosNeg(tree(Left,Root,Right),[Root|Pos],Neg,Other) :- 
    Root >= 0, 
    treePosNeg(Left,List1), 
    treePosNeg(Right,List2), 
    append(List1,List2,Pos). 


treePosNeg(tree(Left,Root,Right),Pos,[Root|Neg],Other) :- 
    Root < 0, 
    treePosNeg(Left,List1), 
    treePosNeg(Right,List2), 
    append(List1,List2,Neg). 

treePosNeg(tree(Left,Root,Right),Pos,Neg,[Root|Other]) :- 
    treePosNeg(Left,List1), 
    treePosNeg(Right,List2), 
    append(List1,List2,Other). 

しかし、私は単に自分の出力としては得られません。私は問題はそれが依然として再帰的に追加する前にtreePosNegを呼び出すことだと思いますが、List1要素とList2要素をインスタンス化してから使用できるようにする必要があります。私はまだPrologにはとても新しいので、私の未熟さに耐えてください！

Answer 1

私は2引数のバージョンを気にせず、4を固定しています。あなたの解決策では、単純すぎるために多くのケースが失われています。たとえば、ここに：

treePosNeg(tree(Left,Root,Right),[Root|Pos],Neg,Other) :- 
    Root >= 0, 
    treePosNeg(Left,List1), 
    treePosNeg(Right,List2), 
    append(List1,List2,Pos). 

あなたがtreePosNeg/2まで簡素化し、Posにすべてを追加。これは、LeftとRightツリーに負のメンバーまたは非数値のメンバーが存在する場合は処理しません。

ここでは、かなり明確にすべき単純で透明な解決策があります。改善を行うことができる（例えば、選択点を避けるなど）。このクエリを実行する

は

% tree_pos_neg(Tree, Pos, Neg, Other) 

% A void tree  
tree_pos_neg(void, [], [], []). 

% A tree where the head node is positive 
tree_pos_neg(tree(L, V, R), [V|Pos], Neg, Other) :- 
    number(V), 
    V >= 0, 
    subtrees_pos_neg(L, R, Pos, Neg, Other). 

% A tree where the head node is negative 
tree_pos_neg(tree(L, V, R), Pos, [V|Neg], Other) :- 
    number(V), 
    V < 0, 
    subtrees_pos_neg(L, R, Pos, Neg, Other). 

% A tree where the head node is neither a positive nor a negative number 
% (it could be *anything* else) 
tree_pos_neg(tree(L, V, R), Pos, Neg, [V|Other]) :- 
    \+ number(V), 
    subtrees_pos_neg(L, R, Pos, Neg, Other). 

subtrees_pos_neg(L, R, Pos, Neg, Other) :- 
    tree_pos_neg(L, LP, LN, LO), 
    tree_pos_neg(R, RP, RN, RO), 
    append(LP, RP, Pos), 
    append(LN, RN, Neg), 
    append(LO, RO, Other). 

、あなたが得る：

| ?- tree_pos_neg(tree(tree(void,a,void),-10,tree(void,b,void)), P, N, O). 

N = [-10] 
O = [a,b] 
P = [] ? ; 

no 
| ?- 

---

は、私は本当に非負意味に変化し、正のあなたの定義に気づいたので、私はそれに応じて私の答えを更新しました。