Is there a way to implement a Prolog program that receives as input a list of integers and create a binary search tree? If the input is 3 6 1 5 the program should output (node 3 null) (node 6 3) (node 1 3) (node 5 6), the output is one node at a time, including its parent.
1 Answers
Trees already exist in the SWI-Prolog library(assoc): Association lists.
Example:
?- empty_assoc(Tree0),put_assoc(3,Tree0,three,Tree1),put_assoc(6,Tree1,six,Tree2),put_assoc(1,Tree2,one,Tree3),put_assoc(5,Tree3,five,Tree).
Tree0 = t,
Tree1 = t(3, three, -, t, t),
Tree2 = t(3, three, >, t, t(6, six, -, t, t)),
Tree3 = t(3, three, -, t(1, one, -, t, t), t(6, six, -, t, t)),
Tree = t(3, three, >, t(1, one, -, t, t), t(6, six, <, t(5, five, -, t, t), t)).
The tree is implemented as as AVL tree which is a balanced binary tree.
Related