在 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 和 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.

我的计划是检查每个子树是否满足合适的要求:我们可以细化每个节点的要求，记住我们是哪些值之间，然后在每个 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.

什么是要求?这是树中值的宽松下限和上限.为了表达需求，包括最左端和最右端的需求，我们可以使用 Bottom 和 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

计算每个子树中的实际极值，将它们向外冒泡，为您提供比您需要的更多的信息，并且在左子树或右子树为空的边缘情况下很繁琐.维护和检查需求，将它们向内推，更加统一.

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屋！