在Haskell中，如何返回二叉树中的节点数

Question

为二叉树类型tree定义一个返回节点数的函数。我想出了这个函数，但它没有运行。

错误：不在范围内：数据构造器"节点">

numberOfNodes :: Tree -> Int
numberOfNodes Null = 0
numberOfNodes (Node _ st1 st2) = 1 + max (st1)(st2)

Answer 1

第一个问题是您似乎缺少树的定义。

通常我们说它要么是一个值加两个子树的Node，要么是空的。

接下来，我们对(非空(树中节点数量的递归定义应该是：

number of nodes in left subtree+number of nodes in right subtree+1

以下是完整的定义：

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
numberOfNodes :: Tree x -> Int
numberOfNodes Empty = 0
numberOfNodes (Node _ st1 st2) = 1 + numberOfNodes(st1) + numberOfNodes(st2)

(注意，我们实现了Show类型类，这样我们就可以打印树(

如果我们定义一个有3个节点的二叉树，看看它是如何工作的：

myTree :: Tree Int
myTree =
Node 0
(Node 1 Empty Empty)
(Node 2 Empty Empty)

> numberOfNodes myTree
=> 3

现场演示

Answer 2

错误表明您没有生成数据构造函数Node。也许您制作了一个数据构造函数Tree，例如：

data Tree a = Null |Treea (Tree a) (Tree a)

使用Tree作为数据构造函数并不是错误的。但您需要决定名称，并使用该数据构造函数。

无论如何，您不需要定义一个函数来自己计算元素的数量。您可以让Haskell将其作为Foldable的实例，然后使用length :: Foldable f => f a -> Int:

{-# LANGUAGE DeriveFoldable #-}
data Tree a = Null | Node a (Tree a) (Tree a) deriving (Foldable, Show)

例如，如果我们定义一个像@AndyG-writed这样的样本树，我们可以将Nodes的数量计算为：

Prelude> length (Node 0 (Node 1 Null Null) (Node 2 Null Null))
3

如果您自己实现长度，您应该对子树进行递归调用，因为您不能将子树相加：

numberOfNodes :: Tree -> Int
numberOfNodes Null = 0
numberOfNodes (Node _ st1 st2) =1 + numberOfNodes st1 + numberOfNodes st2

Answer 3

范围中似乎没有数据类型定义。可能是

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

此外，您显示的代码计算树的深度^{&hairsp；(原则上，在它被固定之后(}。树的节点总数是其左右子树中节点数的和，给定或取1；而不是最大。

可能不应计算空(叶子，Null(节点，即它们对总计数的贡献可能为0。你决定。