Subtrees of a rose tree #
A tree s is a subtree of t when it is rooted at a node of t, reached
from t by descending through children. The relation is a partial order, since a proper subtree
has fewer nodes, and
RoseTree.subtrees lists the subtrees of a tree in preorder, one per node,
which decides the relation. The subtrees are the trees found at the addresses of the tree, as
RoseTree/Get.lean shows.
theorem
RoseTree.IsSubtree.map
{α : Type u_1}
{β : Type u_2}
{s t : RoseTree α}
(f : α → β)
(h : s.IsSubtree t)
:
(RoseTree.map f s).IsSubtree (RoseTree.map f t)
Relabelling preserves the subtree relation.
subtrees t lists the subtrees of t in preorder, t first, one per vertex.
Equations
- (RoseTree.node value cs).subtrees = RoseTree.node value cs :: RoseTree.subtreesList cs
Instances For
subtreesList cs lists the subtrees of the trees of cs.
Equations
- RoseTree.subtreesList [] = []
- RoseTree.subtreesList (c :: cs) = c.subtrees ++ RoseTree.subtreesList cs
Instances For
theorem
RoseTree.subtreesList_eq
{α : Type u_1}
(cs : List (RoseTree α))
:
subtreesList cs = List.flatMap subtrees cs
@[instance_reducible]
instance
RoseTree.instDecidableIsSubtreeOfDecidableEq
{α : Type u_1}
[DecidableEq α]
(s t : RoseTree α)
:
Decidable (s.IsSubtree t)
Equations
- s.instDecidableIsSubtreeOfDecidableEq t = decidable_of_iff (s ∈ t.subtrees) ⋯