#Download swi prolog code
To do this, include sample code and screenshots in your readme.html. Substitute(X, Y, TreeX, TreeY) is true where TreeY is the result of replacing all occurrences of X in TreeX by element Y.įor each of the rules above, you must demonstrate that your implementation is working correctly. Note: TreeOfIntegers does not need to be a binary search tree, so search will have a linear runtime.įor extra credit (see below), implement a binary search predicate ( binsearch) that runs in log time. Search(TreeOfIntegers, Key) is true if element Key appears in TreeOfIntegers which is a binary tree of integers. Hint: two helper rules will be useful: bigger(X, Tree) and smaller(X, Tree), where X is bigger or smaller (respectively) than every element in Tree. Ordered(TreeOfIntegers) verifies if TreeOfIntegers is a binary search tree without duplicates. Sumtree(TreeOfIntegers, Sum) is used to either calculate or verify the sum ( Sum) of integer elements of TreeOfIntegers, which is bound on entry. Note that any tree is a subtree of itself, and therefore subtree(T, T). Subtree(S, T) is true when S is a subtree of T. Tree will be a bound variable on entry, but In can be unbound. Inorder(Tree, In) is true when In is a list containing an inorder traversal of Tree. % Pre is a list of all elements of Tree ordered by a preorder traversal Tree traversal can also be defined logically and translated simply into Prolog. Tree_member(X, tree(_, _, Right)) :- tree_member(X, Right). Tree_member(X, tree(_, Left, _)) :- tree_member(X, Left). % Element is an element of the binary tree Tree The following Prolog rule results: % tree_member(Element, Tree) It is easy to use the recursive definition of binary tree to define what it means for an element to be in a tree. % binary_tree(Tree)īinary_tree(tree(Element, Left, Right)) :. The first element in the structure (root of the tree) is arbitrary, but the second and third elements (children) must themselves be binary trees. tree(1, tree(2, void, void), tree(3, void, void)).īelow is an example of a more complex binary tree. We can define even more carefully a binary tree to consist of a root and two children that are either binary trees (recursive definition) or void to denote an empty tree. However the children ( left_child and right_child) could be anything.Ī better definition would require that the children are defined as trees. ).īinary trees have only two children, a left child and a right child.Ī simple structure for a binary tree might be tree(root, left_child, right_child). Tree RepresentationĪ Prolog structure may be used to represent a tree. The course Moodle page contains links to reference material, SWI-Prolog, and a file containing the starting point code for this assignment as well as some test data. for legal details.įor built-in help, use ?- help(Topic). SWI-Prolog comes with ABSOLUTELY NO WARRANTY. Welcome to SWI-Prolog (threaded, 64 bits, version 8.0.2)
#Download swi prolog download
Download the starter Prolog code from link.SWI-Prolog can be downloaded and ran without installation on your own machine, too.
#Download swi prolog install
0 kommentar(er)
