芯有所想

精益求精

about

数据结构中的满二叉树遍历用Haskell建模

无意中翻到大学的一本书：严蔚明的《数据结构》，其中有一段讲到了用二叉树的遍历来产生集合的所有子集，抽空用简单的Haskell语言写了一个程序，将这个算法简单的体现出来，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

module Main
        where
        data BinaryTree a = Leaf a
                            | Branch (BinaryTree a) a (BinaryTree a) deriving (Show)
        treeHeight (Leaf xs) = 1
        treeHeight (Branch left rs right) = 1 + (max (treeHeight left) (treeHeight right))
        
        -- 数据结构(严蔚明)page148
        -- 数增加一级深度
        append x (Leaf xs) = Branch (Leaf (x:xs)) xs (Leaf xs)
        append x (Branch left rs right) = 
                Branch (append x left) rs (append x right)

        --构造满二叉树
        powerset::Int -> (BinaryTree [Int])
        powerset 0 = Leaf []
        powerset n = append n (powerset (n - 1))

        -- leafnode获得树的所有叶子结点。
        leafnode (Leaf xs) = show xs
        leafnode (Branch left rs right) = (leafnode left) ++ (leafnode right)

        main = putStrLn $ leafnode (powerset 3)

编译运行方式：

ghc –make powerset.hs

​ 生成可执行文件 powerset.exe, 然后运行即可产生书上描述的深度为3的树遍历后所有叶子结点，正好就是{1,2,3}的所有子集。

用Haskell来学习数据结构和算法看来很方便, 特别是递归的算法。