将二叉树元素排序到Prolog中的列表中？

我试图将一棵二叉树排序成3个列表，一个用于正数，一个用于负数，另一个用于其他任何东西。将二叉树元素排序到Prolog中的列表中？

我有了这个代码成功转换成树的列表：

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，根< 0，否则进入另一个列表。我试图使用treePosNeg的三个谓词，每个都检查它们的具体类型。

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仍然很陌生，所以请耐心等待我的经验不足！

来源

2017-10-10 Ruhe

您需要注意您为'treePosNeg'使用了多少个参数。有时候你有2个，有时候是4个。这些在Prolog中是不同的谓词这不一定是一个错误的事情，但它看起来并不像你设计意图那样。 “排序”是什么意思？以什么方式排序？为什么'Root> 10'？ 10的特别之处是什么？ – lurker

我不打扰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 
| ?-

我只注意到你的积极的定义改变为真正意义非负，所以我相应地更新我的答案。

来源

2017-10-11 13:44:13 lurker

将二叉树元素排序到Prolog中的列表中？

回答

相关问题