Prolog Programming -> Binary Tree to list. Implement the predicate treeToList(X,

Question

Prolog Programming -> Binary Tree to list.

Implement the predicate treeToList(X,List), where X is a given ordered non-empty binary tree, and List is an ordered list of elements in nodes of the tree.

Partial Solution Provided:

treeToList(X,List) :- binaryTree(X), convert(X,List).

/* The helping predicate convert(X,List) is true if X is a given non-empty tree, and List is a representation of this tree as an ordered list. */

convert( tree(Element,void,void), List) :- List=[Element]. /* Leaf in a tree */

/* Write the recursive rule and finish the answer */

convert( tree(Root,Left,Right), List) :- ???????????

Explanation / Answer

construct a predicate that unifies with all positive numbers in a tree. Like:

This is prefix notation where we unify with X as the first of the three clauses. In case you want infix, you can swap the first and second prediate. In case postfix is required, then we can swap the first and third clause.

Now we can use the findall/3 meta-predicate:

The advantage of constructing such a positive/2 predicate, is that we can also construct (partially grounded) trees that contain the positive number (with positive(T,3). for instance), further ground a partially grounded tree that should contain a positive number (like T = tree(empty,3,_), positive(T,5).), and furthermore query if a positive number is in the tree (with positive(tree(void,3,void),2).).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.