list of the values in the leaf nodes of binary tree T

by

Let’s use a DCG – a Definite Clause Grammar. We start with your original definition:

lea(T, L) :-
   phrase(values(T), L).

values(nil) -->
   [].
values(t(X,L,R)) -->
   [X],
   values(L),
   values(R).

Now, we need to restrict ourselves to those t/3 that are leaves. One possibility is to enumerate all cases:

lea2(T, L) :-
   phrase(leaves(T), L).

leaves(nil) -->
   [].
leaves(t(X,nil,nil)) -->
   [X].
leaves(t(_,L,R)) -->
   { dif(L+R,nil+nil) },
   leaves(L),
   leaves(R).

It would be even better and more efficient to use a conditional construct similar to if_/3. I want to leave this to someone interested.

More Related Contents:

  1. What is the difference between ‘ and ” in Prolog?
  2. Stack overflow in Prolog DCG grammar rule: how to handle large lists efficiently or lazily
  3. Prolog map procedure that applies predicate to list elements
  4. Definition of a path/trail/walk
  5. Definition of Reflexive Transitive Closure
  6. Most general higher-order constraint describing a sequence of integers ordered with respect to a relation
  7. Delete vowels in a list
  8. Prolog successor notation yields incomplete result and infinite loop
  9. Finding Unique Items in a List
  10. Prolog: a person is a sibling of himself?
  11. What is the logical ‘not’ in Prolog?
  12. Flatten a list in Prolog
  13. Einsteins Riddle Prolog
  14. Complexity of ISO Prolog predicates
  15. Read a file line by line in Prolog
  16. Get elements from list of lists
  17. Explanation of a Prolog algorithm to append two lists together
  18. reversible “binary to number” predicate
  19. Collect all “minimum” solutions from a predicate
  20. Using \==/2 or dif/2
  21. Good beginners material on Prolog [closed]
  22. ‘if’ in prolog?
  23. Should I avoid tail recursion in Prolog and in general?
  24. Prolog append with cut operator
  25. Define graph in Prolog: edge and path, finding if there is a path between two vertices
  26. Can you write between/3 in pure prolog?
  27. PROLOG: Determining if elements in list are equal if order does not matter
  28. Recursive Prolog predicate for reverse / palindrome
  29. Prolog getting head and tail of string
  30. GNU Prolog assert error

Leave a Comment