Trees, like lists, are an application of Scheme pairs. An atom is any Scheme object that is not a pair. A tree is a non-empty list whose elements are either trees or atoms. Trees cannot be circular. The atoms and subtrees of a tree are called its nodes. The words parent, child, ancestor, descendant, sibling are used with the usual meanings.
Although the empty list is an atom, it's a bad idea to make use of it in trees, as it may confuse list-oriented procedures that treat it as a list.
(tree? obj)
Returns #t if obj is a tree, and #f otherwise.
(atom? obj)
Returns #t if obj is an atom, and #f otherwise.
(tree-contains? tree node)
Returns #t if node is the same (in the sense of eqv?) as a node of tree, and #f otherwise. This can also be used to determine if tree is an ancestor of node.
(tree-c-commands? tree commanding commanded)
If the subtree commanding c-commands the subtree commanded in tree, returns #t; otherwise returns #f. It is an error if either ancestor or descendant is not a subtree of tree.
A node in a tree c-commands its sibling node(s) and all of its siblings' descendants; however, a node without siblings c-commands everything that its parent node c-commands.
(tree=? same? tree1 tree2)
Returns #t if tree1 and tree2 are isomorphic and their atoms are the same in the sense of same?, and #f otherwise.
(tree-depth-of tree subtree)
Returns the depth of subtree within tree as an exact integer. If tree and subtree are the same in the sense of eqv?, returns 0.
(tree-depth tree)
Returns the maximum depth of tree as an exact integer.
(tree-parent tree node)
Returns the parent node of node within tree. This involves a search from tree. Returns #f if node is not a descendant of tree.
(tree-path tree subtree)
Returns a list of nodes containing subtree and all the ancestors of subtree ending with tree. Returns #f if subtree is not a descendant of tree.
(tree-copy tree)
Return a copy of tree. Atoms are shared, but tree structure is not.
(tree-map proc tree)
Returns a copy of tree, except that each descendant atom has been passed through proc. Tree structure is not shared.'
The following functions examine all nodes in the tree in an unspecified order. Pred is a predicate which has no side effects and always returns the same result on the same argument.
(tree-size tree)
Returns the number of atoms in tree as an exact integer.
(tree-count pred tree)
Returns the number of nodes of tree that satisfy pred as an exact integer.
(tree-any? pred tree)
Examines the nodes of tree to determine if any of them satisfy pred.
(tree-every? pred tree)
Returns the number of nodes of tree to determine if all of them satisfy pred.
The following procedures return finite SRFI 121 generators that return some of the nodes of a tree in any of a variety of orders. When all the nodes have been returned, the generator returns an EOF object.
(tree-make-preorder-generator [tree)
Returns a generator that when invoked returns the nodes of tree in depth-first preorder: parents are generated before children, and children are generated in left-to-right order.
(tree-make-postorder-generator tree)
Returns a generator that when invoked returns the nodes of tree in depth-first postorder: children are generated in left-to-right order and then their parent is generated.
(tree-make-breadthfirst-generator tree)
Returns a generator that when invoked returns the nodes of tree in breadth-first order: tree is generated, then all children of tree in left-to-right order, then all grandchildren of tree in left-to-right order, and so on.
(tree-make-atom-generator tree)
Returns a generator that when invoked returns pairs, where the car of each pair is an atomic descendant of tree, and the cdr of each pair is the depth of that atom. The order of generation is depth-first postorder.
(atom-generator->tree generator)
Returns a reconstituted tree from the values of generator, which generates pairs of the type created by a tree-make-atom-generator generator. The result is tree=? to tree with an atomic comparison of eqv?.
These procedures do not mutate the tree they work on, but return a new tree isomorphic to the old tree and with the same elements, except as specified below. The new tree may share storage with the old.
(tree-add tree subtree newnode)
Returns a tree where node has an additional child, newnode, which is placed to the right of all existing children. It is an error if subtree is not a descendant of tree or if newnode is a non-atomic descendant of tree.
(tree-insert tree subtree index newnode)
Returns a tree where subtree has an additional child, newnode, which is placed immediately to the left of the child whose position in subtree is index (an exact integer). It is an error if subtree is not a descendant of tree, if newnode is a non-atomic descendant of tree, or if index is greater than or equal to the number of child nodes of subtree.
(tree-prune tree subtree)
Returns a tree where subtree and all its descendants are not part of the new tree. It is an error if subtree is not a descendant of tree.
(tree-replace tree subtree newnode)
Returns a tree where node has been replaced by newnode in the new tree. It is an error if subtree is not a descendant of tree or if newnode is already a non-atomic descendant of tree.
(tree-number-preorder tree)
Return a tree that is isomorphic to tree, except that every subtree has a new first child prepended to its existing children. This child is an exact integer, starting at 0 for the root and <i>n</i> - 1 for the last child in depth-first preorder, where <i>n</i> is the number of subtrees of tree.
(tree-number-postorder tree)
Return a tree that is isomorphic to tree, except that every subtree has a new first child prepended to its existing children. This child is an exact integer, starting at 0 for the root and <i>n</i> - 1 for the last child in postorder, where <i>n</i> is the number of subtrees of tree.
(tree-number-depth-firstr tree)
Return a tree that is isomorphic to tree, except that every subtree has a new first child prepended to its existing children. This child is an exact integer, starting at 0 for the root and <i>n</i> - 1 for the last child in depth-first order, where <i>n</i> is the number of subtrees of tree.
(tree-display-atoms tree [ port ])
Walks through the atoms of tree in breadth-first order and displays them (as if using display) on port, which defaults to the value of (current-output-port).