haskell - 在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，然后对列表进行排序以查找它们是否相等，但是这有点复杂。我们可以在不导入其他模块的情况下做到这一点吗？

最佳答案

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

根据定义，

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

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

我的计划是检查每个子树是否满足合适的需求:我们可以在每个Node处完善需求，记住我们之间的值，然后在每个Null处对其进行测试。由于在每个有序的值对之间都有一个Null，我们将测试所有有序的(从左至右)对都是不递减的。

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

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

现在让我们检查给定的树是否满足顺序和在给定范围之间的要求。

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之间的树。

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

计算每个子树中的实际极值，使其向外冒泡，会为您提供比您所需更多的信息，并且在左侧或右侧子树为空的边缘情况下比较麻烦。维护和检查需求，将其向内推，则更加统一。

关于haskell - 在Haskell中查找树是否为二叉搜索树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58304077/