August 19, 2024
P70B - Check whether a given expression represents a multiway tree
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 Lisp we represent a multiway tree by either a symbol (root with no children) or by an expression (X C1 C2 ... CN), where X denotes the root node and Ci denote each of the children. The following pictures show how multiway tree structures are represented in Lisp.
Note that in this Lisp notation a node with successors (children) in the tree is always the first element in a list, followed by its children.
Write a function is tree which succeeds if and only if its argument is a Lisp expression representing a multiway tree.
Example:* (istree '(a (f g) c (b d e)))T
lisp
(defun istree (expr)
(or
(atom expr)
(and
(listp expr)
(>= (length expr) 2)
(atom (car expr))
(alltree (cdr expr))
)
)
)
(defun alltree (lista)
(or
(null lista)
(and (istree (car lista)) (alltree (cdr lista)))
)
)