Math.Combinat.Trees.Nary

N-ary trees.

regular trees

ternaryTrees :: Int -> [Tree ()]

Ternary trees on n nodes (synonym for regularNaryTrees 3)

regularNaryTrees

Arguments

:: Int

degree = number of children of each node

-> Int

number of nodes

-> [Tree ()]

regularNaryTrees d n returns the list of (rooted) trees on n nodes where each node has exactly d children. Note that the leaves do not count in n. Naive algorithm.

semiRegularTrees

Arguments

:: [Int]

set of allowed number of children

-> Int

number of nodes

-> [Tree ()]

All trees on n nodes where the number of children of all nodes is in element of the given set. Example:

 mapM_ printTreeVertical 
  $ map labelNChildrenTree_ 
  $ semiRegularTrees [2,3] n

 [ length $ semiRegularTrees [2,3] n | n<-[0..] ] == [1,2,10,66,498,4066,34970,312066,2862562,26824386,...]

The latter sequence is A027307 in OEIS: https://oeis.org/A027307

Remark: clearly, we have

 semiRegularTrees [d] n == regularNaryTrees d n

countTernaryTrees :: Integral a => a -> Integer

# = \frac {1} {(2n+1} \binom {3n} {n}

countRegularNaryTrees :: (Integral a, Integral b) => a -> b -> Integer

We have

 length (regularNaryTrees d n) == countRegularNaryTrees d n == \frac {1} {(d-1)n+1} \binom {dn} {n} 

derivation trees

derivTrees :: [Int] -> [Tree ()]

Computes the set of equivalence classes of rooted trees (in the sense that the leaves of a node are unordered) with n = length ks leaves where the set of heights of the leaves matches the given set of numbers. The height is defined as the number of edges from the leaf to the root.

TODO: better name?

ASCII drawings

printTreeVertical_ :: Tree a -> IO ()

Vertical ASCII drawing of a tree, without labels.

Example:

 mapM_ printTreeVertical_ $ regularNaryTrees 2 3 

printTreeVertical :: Show a => Tree a -> IO ()

Prints all labels.

Example:

 printTreeVertical $ addUniqueLabelsTree_ $ (regularNaryTrees 3 9) !! 666

printTreeVerticalLeavesOnly :: Show a => Tree a -> IO ()

Prints the labels for the leaves, but not for the nonempty nodes

drawTreeVertical_ :: Tree a -> String

Nodes are denoted by @, leaves by *.

drawTreeVertical :: Show a => Tree a -> String

Nodes are denoted by (label), leaves by label.

drawTreeVerticalLeavesOnly :: Show a => Tree a -> String

Nodes are denoted by @, leaves by label.

classifying nodes

classifyTreeNode :: Tree a -> Either a a

Left is leaf, Right is node

isTreeLeaf :: Tree a -> Maybe a

isTreeNode :: Tree a -> Maybe a

isTreeLeaf_ :: Tree a -> Bool

isTreeNode_ :: Tree a -> Bool

treeNodeNumberOfChildren :: Tree a -> Int

counting nodes

countTreeNodes :: Tree a -> Int

countTreeLeaves :: Tree a -> Int

countTreeLabelsWith :: (a -> Bool) -> Tree a -> Int

countTreeNodesWith :: (Tree a -> Bool) -> Tree a -> Int

left and right spines

leftSpine :: Tree a -> ([a], a)

The leftmost spine (the second element of the pair is the leaf node)

leftSpine_ :: Tree a -> [a]

The leftmost spine without the leaf node

rightSpine :: Tree a -> ([a], a)

rightSpine_ :: Tree a -> [a]

leftSpineLength :: Tree a -> Int

The length (number of edges) on the left spine

 leftSpineLength tree == length (leftSpine_ tree)

rightSpineLength :: Tree a -> Int

unique labels

addUniqueLabelsTree :: Tree a -> Tree (a, Int)

Adds unique labels to the nodes (including leaves) of a Tree.

addUniqueLabelsForest :: Forest a -> Forest (a, Int)

Adds unique labels to the nodes (including leaves) of a Forest

addUniqueLabelsTree_ :: Tree a -> Tree Int

addUniqueLabelsForest_ :: Forest a -> Forest Int

labelling by depth

labelDepthTree :: Tree a -> Tree (a, Int)

Attaches the depth to each node. The depth of the root is 0.

labelDepthForest :: Forest a -> Forest (a, Int)

labelDepthTree_ :: Tree a -> Tree Int

labelDepthForest_ :: Forest a -> Forest Int

labelling by number of children

labelNChildrenTree :: Tree a -> Tree (a, Int)

Attaches the number of children to each node.

labelNChildrenForest :: Forest a -> Forest (a, Int)

labelNChildrenTree_ :: Tree a -> Tree Int

labelNChildrenForest_ :: Forest a -> Forest Int