P54 - 定义二叉树
Binary trees
官方模块：
Problems.P54核心类型：Tree
数据类型
二叉树要么为空，要么是一个携带值且恰有左右两棵子树的分支。
1data Tree a
2 = Empty
3 | Branch a (Tree a) (Tree a)
4 deriving (Eq, Show)
5
6leaf :: a -> Tree a
7leaf x = Branch x Empty Empty
类型参数 a 表示节点值类型；树的形状与节点值彼此独立。leaf 不是新构造器，只是常用结构的辅助函数。
示例树
1tree1 :: Tree Char
2tree1 = Branch 'a'
3 (Branch 'b' (leaf 'd') (leaf 'e'))
4 (Branch 'c' Empty (Branch 'f' (leaf 'g') Empty))
5
6tree2 :: Tree Char
7tree2 = leaf 'a'
8
9tree3 :: Tree Char
10tree3 = Empty
11
12tree4 :: Tree Int
13tree4 = Branch 1 (Branch 2 Empty (leaf 4)) (leaf 2)
基础度量
方法一：treeSize 递归计数
1treeSize :: Tree a -> Int
2treeSize Empty = 0
3treeSize (Branch _ l r) = 1 + treeSize l + treeSize r
treeHeight：递归取最大深度
1treeHeight :: Tree a -> Int
2treeHeight Empty = 0
3treeHeight (Branch _ l r) = 1 + max (treeHeight l) (treeHeight r)
方法二：treeSize 显式栈
1treeSize :: Tree a -> Int
2treeSize tree = go [tree] 0
3 where
4 go [] acc = acc
5 go (Empty : rest) acc = go rest acc
6 go (Branch _ l r : rest) acc = go (l : r : rest) (acc + 1)
显式使用栈代替递归，遍历所有节点时计数。对于极深的树可以避免栈溢出。
方法三：treeSize 用 fold 风格
1treeSize :: Tree a -> Int
2treeSize = foldTree (\_ l r -> 1 + l + r)
3 where
4 foldTree :: (a -> Int -> Int -> Int) -> Tree a -> Int
5 foldTree _ Empty = 0
6 foldTree f (Branch x l r) = f x (foldTree f l) (foldTree f r)
测试
1>>> treeSize tree1
27
3>>> treeHeight tree1
44
5>>> tree2 == leaf 'a'
6True