Haskell：实现⼆叉树及其前序、中序、后序遍历和层序遍历
⽤函数式编程语⾔实现数据结构，是⾮常返璞归真的⼀件事情。
树的定义
⽤参数化类型定义⼆叉树。
data Tree a =Empty|Node(Tree a) a (Tree a) deriving (Show)
多叉树可以⽤左孩⼦右兄弟来表⽰。在此基础上，森林可以⽤“所有的树有共同的根节点”表⽰成⼀棵多叉树，从⽽⽤左孩⼦右兄弟表⽰成⼆叉树。（或者⼆叉树森林⽤“左第⼀右其余”表⽰成⼆叉树。）
树的性质（类型类）
顺⼿给出树遵从的类型类。下⽂除了toList之外，与本节⽆关，阅读时可以跳过。
instance Foldable Tree where
-- foldMap ::Monoid m =>(a -> m)->Tree a -> m
foldMap f Empty= mempty
foldMap f (Node l k r)= foldMap f l `mappend` f k `mappend` foldMap f r
instance Functor Tree where
-- fmap ::(a -> b)->Tree a ->Tree b
fmap f Empty=Empty
fmap f (Node l k r)=Node(fmap f l)(f k)(fmap f r)
instance Traversable Tree where
-- traverse ::(Traversable t,Applicative f)=>(a -> f b)->Tree a -> f (Tree b)
traverse f Empty= pure Empty
traverse f (Node l k r)=Node<$> traverse f l <*> f k <*> traverse f r
前中后序遍历
简单递归即可。
import Data.Foldable-- toList
preOrderTraversal ::Tree a ->[a]
preOrderTraversal Empty=[]
preOrderTraversal (Node l k r)=
k:(preOrderTraversal l)++ preOrderTraversal r
inOrderTraversal ::Tree a ->[a]
inOrderTraversal = toList
postOrderTraversal ::Tree a ->[a]
postOrderTraversal Empty=[]
postOrderTraversal (Node l k r)=
postOrderTraversal l ++ postOrderTraversal r ++[k]
注意中序遍历对库函数List的使⽤。因为data Tree的结构限制，三种遍历顺序中总是只有⼀种能使⽤库函数，剩下两种结构需要重写⼀遍。
层序遍历
思路是bfs：使⽤⼀个队列（这⾥⽤列表模拟），⼀开始队列中只有原树，每次取出队⾸的树，将其根节点加⼊输出列表，将其左右⼦树加⼊队列末尾。队列为空时停⽌。
我们使⽤⼀个尾递归来描述每⼀步的操作。尾递归可以保存状态，最适合这种⼀步⼀步改变状态的场景。（进⼀步地，如果是⼀个会失败的操作，可以⽤state monad)
levelOrderTraversal ::Tree a ->[a]
levelOrderTraversal tree =reverse $ step ([],[tree])
where
step (result, trees)=case trees of
[]-> result
Empty:ts -> step (result, ts)
(Node l k r):ts -> step (k:result, ts++[l, r])
注意到，输出列表在尾递归过程中是倒序存储的，以便使⽤默认构造函数(:)提升效率。在最终返回时reverse成正序。
先序中序后序遍历二叉树
测试
testTree =Node(Node(Node Empty4Empty)2Empty)1(Node Empty10(Node Empty15Empty))
testList =map($ testTree)[preOrderTraversal, inOrderTraversal, postOrderTraversal, levelOrderTraversal]
-- testList ==[[1,2,4,10,15],[4,2,1,10,15],[4,2,15,10,1],[1,2,10,4,15]]
⽬前CSDN不⽀持Haskell的⾼亮。在⽬前⽀持的⾼亮样式中，似乎使⽤swift的⾼亮效果⽐较好 还是知乎和Gitee⽐较⾹orz

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。