CODEWITHSUNDEEP
treeprologbinary-tree
bttX
bttX

Reputation: 33

Prolog verification of a binary trees

I am a beginner with prolog and I want to write a predicate that turns true if the argument is a tree. I have this code but it gives me always false. can anyone help me pls.

arb_true(nil).
arb_true([X,G,D]):- X=[_,G,D], arb_true(G), arb_true(D).

the query is arb_true([6,[4,[1,[],[]],[]],[9,[],[]]]).

Upvotes: 1

Views: 1973

Answers (2)

user1812457
user1812457

Reputation:

Usually, you don't represent a tree as a list of three elements, but a term with three arguments. And any way you decide to represent a tree, you need to be consistent. In your current (I assume not working?) solution, you have nicely mixed two different ways you could represent a tree.

Here is one way to represent a binary tree: an empty tree would be the atom nil, and a non-empty tree would be the term tree(Value, Left, Right). So:

binary_tree(nil).
binary_tree(t(_, L, R)) :-
    binary_tree(L),
    binary_tree(R).

Or, if you choose to use lists with three elements [Value, Left, Right], and the empty list [] as an empty tree, you would have:

binary_tree([]).
binary_tree([_, L, R]) :-
    binary_tree(L),
    binary_tree(R).

I'd say the first representation is the more usual one. In both cases, if you just want to check whether it is a binary tree, you can (and should) ignore the "value" (the first argument in tree(Value, Left, Right) or the first element of [Value, Left, Right].

However: your example shows a binary three that is also sorted binary tree, or a binary search tree. To validate whether you have that, you would need to compare the actual values in the left and right subtrees. This is not currently part of your question so you need to edit it with the necessary detail.

Upvotes: 4

coder
coder

Reputation: 12992

You have defined the clause arb_true(nil). but you represent the empty tree with empty list and not with 'nil' so you need to write:

arb_true([]).

Also you need to write:

arb_true([_,G,D]):-arb_true(G), arb_true(D).

instead of:

arb_true([X,G,D]):- X=[_,G,D], arb_true(G), arb_true(D).

Now querying arb_true([6,[4,[1,[],[]],[]],[9,[],[]]]). :

 ?- arb_true([6,[4,[1,[],[]],[]],[9,[],[]]]).
true.

Upvotes: 0

Related Questions