遗传排序的Haskell二叉树谓词

Question

对哈斯克尔来说真的很新鲜，我想不通。如何检查给定二叉树中的节点是否大于其子节点？

module IntTree where

data IntTree = Leaf Int
             | Node Int IntTree IntTree
             deriving (Eq,Show)

t1 :: IntTree
t1 = Node 1999 (Node 1963 (Leaf 1925)
                          (Leaf 1933))
               (Node 1956 (Leaf 1932)
                          (Leaf 1924))


t2 :: IntTree
t2 = Node 1999 (Node 1922 (Leaf 1925)
                          (Leaf 1933))
               (Node 1956 (Leaf 1932)
                          (Leaf 1924))

descendingTree :: Ord a => IntTree -> Bool

函数< code>descendingTree将获得一个< code>IntTree并将返回给我一个Boolean值，表明对于树中的每个节点，该节点的值是否大于其两个子节点的值；如果它有孩子的话。这个函数怎么写？

Answer 1

答案是 ：慢慢地 直接遵循你的数据类型定义。

descendingTree :: IntTree -> Bool     -- no `a`, so no `Ord a` too
-- data IntTree = Leaf Int
descendingTree   (Leaf i) = leaf i
--              | Node Int IntTree IntTree
descendingTree   (Node  i     lt     rt  ) = node i lt rt

如果是叶子，就没什么好检查的了:

leaf _ = True

如果它是一个节点，它总是有两个子节点；这是由它的类型定义保证的。类型中没有其他可能性。

node i lt rt = 

在这里，您需要填写您的测试：

        i > value lt &&
        i > value rt &&

这两个检查将被完成；如果一个失败了整个

        every_node_is_greater .... &&
        every_node_is_greater ....

你能填空吗？

能写出< code > every _ node _ is _ greater 的定义吗？你需要吗？

当然，函数< code>leaf和< code>node是完全冗余的；它们在这里只充当了精神上的垫脚石，为我们清除了写作的障碍。:)您通常将代码写在< code>descendingTree定义中相应的子句中。

这里还需要为value编写一个定义，这是我们在探索问题空间时引入的新抽象（“如果我们有办法知道节点的“值”呢？我们稍后会处理细节…”）。现在终于是充实它的时候了。同样，简单地（缓慢地）遵循类型，并处理它呈现的案例。