5. Multiway Trees – Prolog Site
Copyright By PowCoder代写 加微信 powcoder
Prolog Site
Search this site
Prolog Course
1. A First Glimpse
2. Syntax and Meaning
Prolog Problems
1. Prolog Lists
2. Arithmetic
3. Logic and Codes
4. Binary Trees
5. Multiway Trees
7. Miscellaneous
Prolog Problems >
5. Multiway Trees
Solutions can be found
A multiway tree is composed of a root element and
a (possibly empty) set of successors which are multiway trees
themselves. A multiway tree is never empty. The set of successor
trees is sometimes called a forest.
In Prolog we represent a multiway tree by a term t(X,F), where X denotes
the root node and F denotes the forest of successor trees (a Prolog list).
The example tree depicted opposite is therefore represented by the
following Prolog term:
T = t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])
(*) Check whether a given term represents a multiway tree
Write a predicate istree/1 which succeeds if and only if its argument
is a Prolog term representing a multiway tree.
?- istree(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])).
(*) Count the nodes of a multiway tree
Write a predicate nnodes/1 which counts the nodes of a given
multiway tree.
?- nnodes(t(a,[t(f,[])]),N).
Write another version of the predicate that allows
for a flow pattern (o,i).
(**) Tree construction from a node string
We suppose that the nodes of a multiway tree contain single
characters. In the depth-first order sequence of its nodes, a
special character ^ has been inserted whenever, during the
tree traversal, the move is a backtrack to the previous level.
By this rule, the tree in the figure opposite is
represented as: afg^^c^bd^e^^^
Define the syntax of the string and write a predicate tree(String,Tree)
to construct the Tree when the String is given. Work with atoms (instead
of strings). Make your predicate work in both directions.
(*) Determine the internal path length of a tree
We define the internal path length of a multiway tree as the
total sum of the path lengths from the root to all nodes of the tree.
By this definition, the tree in the figure of problem 5.03 has an internal
path length of 9.
Write a predicate ipl(Tree,IPL) for the flow
pattern (+,-).
(*) Construct the bottom-up order sequence of the tree nodes
Write a predicate bottom_up(Tree,Seq) which constructs the
bottom-up sequence of the nodes of the multiway tree Tree. Seq
should be a Prolog list.
What happens if you run your predicate
backwords?
(**) Lisp-like tree representation
There is a particular notation for multiway trees in Lisp.
Lisp is a prominent functional programming language, which is used
primarily for artificial intelligence problems. As such it is one of
the main competitors of Prolog. In Lisp almost everything is a list,
just as in Prolog everything is a term.
The following pictures show how multiway tree structures are
represented in Lisp.
Note that in the “lispy” notation a node with successors (children)
in the tree is always the first element in a list, followed by its
The “lispy” representation of a multiway tree is a sequence of
atoms and parentheses ‘(‘ and ‘)’, which we shall collectively
call “tokens”. We can represent this sequence of tokens
as a Prolog list; e.g. the lispy expression (a (b c)) could be
represented as the Prolog list [‘(‘, a, ‘(‘, b, c, ‘)’, ‘)’].
Write a predicate tree_ltl(T,LTL) which constructs the “lispy
token list” LTL if the tree is given as term T in the usual
Prolog notation.
?- tree_ltl(t(a,[t(b,[]),t(c,[])]),LTL).
LTL = [‘(‘, a, ‘(‘, b, c, ‘)’, ‘)’]
As a second, even more interesting exercise try to rewrite
tree_ltl/2 in a way that the inverse conversion is also
possible: Given the list LTL, construct the Prolog tree T.
Use difference lists.
Subpages (1):
Solutions-5
登录|举报滥用行为|打印页面|由 Google 协作平台强力驱动
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com