haskell - Haskell 中树的数据类型

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列表是链接列表。