Haskell中Tree的数据类型

Question

对于二叉树的数据类型,您可以编写如下内容:

data Tree a = Nil | Node a (Tree a) (Tree a)

因此,如果我想要包含树,而节点只有两个子节点,那么数据类型怎么可能看起来像？

Answer 1

一个鲜为人知的技术是Left-child right-sibling,你可以使用完全相同的类型来编码每个节点有两个以上子节点的树:

data Tree a
  = Nil
  | Node a (Tree a) (Tree a) -- value, left child, right sibling

替代[Tree a]它不具有性能上的优势,因为Haskell的列表是链表.

Answer 2

您可以拥有固定的分支因子:

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

(请注意,QuadTree对于分支因子为4的常规树而言,这不是一个很好的名称,因为存在具有该名称的特定数据结构.)

或者您可以简单地使用玫瑰树,它在每个节点存储任意子列表.

data RoseTree a = RTNil | RTNode a [RoseTree a]

有一些重复,这里,因为RTNil是只需要存储一个明确的空树.叶节点就是RTNode a [].(想想有什么区别,如果有的话,你将会分配给值RTNode 3 [],RTNode 3 [RTNil],RTNode 3 [RTNil, RTNil],等)