在Haskell中查找树是否为二叉搜索树 [英] Find whether a tree is a binary search tree in Haskell

问题描述

  type BSTree a = BinaryTree a

  data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
                      deriving Show

  flattenTree :: BinaryTree a -> [a]
  flattenTree  tree = case tree of
      Null -> []
      Node left val right -> (flattenTree left) ++ [val] ++ (flattenTree right)

  isBSTree :: (Ord a) => BinaryTree a -> Bool
  isBSTree btree = case btree of
      Null -> False
      tree -> (flattenTree tree) == sort (flattenTree tree)

我想做的是编写一个函数来确定给定的树是否是二叉搜索树，我的方法是将所有值分组到一个列表中，然后导入Data.List，然后对列表进行排序以查找是否它们是相等的，但是有点复杂.我们可以在不导入其他模块的情况下做到这一点吗?

What I want to do is to write a function to determine whether the given tree is a binary search tree, my method is to group all of the values in a list and import Data.List and then sort the list to find whether they are equal, but it is a little complicated. Can we do this without importing other module?

推荐答案

这是一种无需展平树的方法.

Here's a way to do it without flattening the tree.

从定义开始，在这里

data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
     deriving Show

可以看到，从树的左到右遍历，忽略了Node和括号，为您提供了Null s和a s的交替序列.也就是说，在每两个值之间有一个Null.

one can see that traversing the tree left to right, ignoring Node and parentheses, gives you an alternating sequence of Nulls and as. That is, between every two values, there is a Null.

我的计划是检查每个子树是否满足适当的要求:我们可以细化每个Node处的要求，记住我们之间的值，然后Null上>测试.由于每个有序的值对之间都有一个Null，我们将测试所有有序的(从左至右)对都不会减少.

My plan is to check that each subtree satisfies suitable requirements: we can refine the requirements at each Node, remembering which values we are between, then test them at each Null. As there is a Null between every in order pair of values, we will have tested that all in order (left-to-right) pairs are non-decreasing.

有什么要求?这是树中值的松散上下限.为了表达需求，包括最左端和最右端的需求，我们可以使用Bot tom和Top元素扩展任何顺序，如下所示:

What is a requirement? It's a loose lower and upper bound on the values in the tree. To express requirements, including those at the leftmost and rightmost ends, we may extend any ordering with Bottom and Top elements, as follows:

data TopBot a = Bot | Val a | Top deriving (Show, Eq, Ord)

现在让我们检查一棵给定的树是否满足在有序和在给定范围之内的要求.

Now let us check that a given tree satisfies the requirements of being both in order and between given bounds.

ordBetween :: Ord a => TopBot a -> TopBot a -> BinaryTree a -> Bool
  -- tighten the demanded bounds, left and right of any Node
ordBetween lo hi (Node l x r) = ordBetween lo (Val x) l && ordBetween (Val x) hi r
  -- check that the demanded bounds are in order when we reach Null
ordBetween lo hi Null         = lo <= hi

二分搜索树是按顺序排列在Bot和Top之间的树.

A binary search tree is a tree that is in order and between Bot and Top.

isBSTree :: Ord a => BinaryTree a -> Bool
isBSTree = ordBetween Bot Top

计算每个子树中的 actual 极值，将它们向外冒泡，会为您提供比您所需更多的信息，并且在左右子树为空的边缘情况下比较麻烦.维护和检查需求并将其向内推，这将变得更加统一.

Computing the actual extremal values in each subtree, bubbling them outwards, gives you more information than you need, and is fiddly in the edge cases where a left or right subtree is empty. Maintaining and checking the requirements, pushing them inwards, is rather more uniform.

这篇关于在Haskell中查找树是否为二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！