For a data type of a binary tree you can write something like this:
data Tree a = Nil | Node a (Tree a) (Tree a)
So if I do want to include trees, with Nodes having more than just two children, how could the data type possibly look like?
-
3The children can be stored. In a list. They are sometimes called "rose trees": hackage.haskell.org/package/containers-0.5.9.1/docs/…danidiaz– danidiaz2016-12-31 14:05:43 +00:00Commented Dec 31, 2016 at 14:05
Add a comment
|
2 Answers
A lesser known technique is Left-child right-sibling where you can use the exact same type to encode trees with more than two children per node:
data Tree a
= Nil
| Node a (Tree a) (Tree a) -- value, left child, right sibling
The alternative [Tree a] does not have a performance advantage, since Haskell lists are linked lists.
Comments
You can either have a fixed branching factor:
data BinaryTree a = BTNil
| BTNode a (BinaryTree a) (BinaryTree a)
data TernaryTree a = TTNil
| TTNode a (TernaryTree a) (TernaryTree a) (TernaryTree a)
data QuadTree a = QTNil
| QTNode a (QuadTree a) (QuadTree a) (QuadTree a) (QuadTree a)
-- etc
(Note that QuadTree isn't a great name for a general tree with a branching factor of 4, since there is a specific data structure with that name.)
or you can simply use a rose tree, which stores an arbitrary list of children at each node.
data RoseTree a = RTNil | RTNode a [RoseTree a]
There is some duplication here, as RTNil is only needed to store an explicit empty tree. Leaf nodes are just RTNode a []. (Consider what difference, if any, you would assign to the values RTNode 3 [], RTNode 3 [RTNil], RTNode 3 [RTNil, RTNil], etc.)
