listprologbinary-treedcgfailure-slice

Prolog binary list issue

I'm working on a binary tree program in Prolog. The specific issue I'm having is with traversals. Here's what I have :

inOrder(bttree(_,L,_),T):-  inOrder(L,T).
inOrder(bttree(N,_,_),T) :- T1 = T, append(T1,N,T).
inOrder(bttree(_,_,R),T):-  inOrder(R,T).

I've been querying it with:

inOrder(bttree(20,
    bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)) bttree(30)), T).

so the output SHOULD be:

[5,10,15,20,30];
false.

But when I run it, it just returns false. I'm fairly certain the problem is in my use of append/3, but I simply can't work it out. If anyone can help, it'd be much appreciated

Solution

  • this T1 = T, append(T1,N,T) is equivalent to append(T,N,T) and doomed to loop...

    some corrections...

    inOrder(nil, []).
inOrder(bttree(N, L, R),T) :-
  inOrder(L, LT),
  inOrder(R, RT),
  append(LT, [N|RT], T).

    test:

    ?- inOrder(bttree(20, bttree(10, bttree(5,nil,nil), bttree(15,nil,nil)), bttree(30,nil,nil)), T).
T = [5, 10, 15, 20, 30].