在二叉树haskell中搜索值

Question

我刚刚开始学习Haskell，我正在尝试编写一个代码来搜索二叉树中的特定值，如果当前返回true，否则返回false这就是我的树结构的样子

data Tree = Leaf Int | Node Tree Int Tree

我不确定如何继续遍历树并返回值的函数。我确实尝试了BFS和DFS，但我不确定一旦得到值后如何返回。

我的函数应该是什么样子的一个例子

Search 5 (Node (Node (Leaf 1) 3 (Leaf 4)) 5 (Node (Leaf 6) 7 (Leaf 9))) 

Answer 1

我不确定如何继续使用函数遍历树并返回值。

从这句话中，我知道你自己编写遍历没有问题，但是你需要做一个心理上的飞跃来理解Haskell是如何工作的。

你看，你从来没有在Haskell中返回任何东西。返回基本上是一个祈使句。Haskell是一种声明性语言，这意味着编写程序是通过陈述事实来完成的。这种细微差别可能会令人不安，尤其是如果你是通过学习祈使句语言（如C、Java、JavaScript等）来了解html" target="_blank">编程的。但是一旦你真正理解了它，你会看到声明性编程有多富有表现力和简单。

由于其强大的数学基础，在Haskell中事实是以方程的形式陈述的，即表达式中的< code>=符号字面上意味着左边和右边是相等的(而在命令式语言中，它可能意味着你给一个变量赋值——这在Haskell中是不存在的)。

@Haleemur Ali编写的程序与使用数学符号编写搜索的方式是1:1的：

search(x, t) = { x == y       if t = Leaf y
               , true         if t = Node l y r and x == y
               , search(x, l) if t = Node l y r and x < y
               , search(x, r) if t = Node l y r and x > y
               }

事实上，很多时候，至少作为一个初学者，编写Haskell只是一个翻译问题，从数学符号到Haskell符号。Haskell程序的另一种解释是作为定理的证明。你的搜索是一个定理，说“如果你有一棵树和一个整数，你总是可以知道这个整数是否在树里面的某个地方”。这就是你写函数签名时告诉编译器的:

search :: Int -> Tree -> Bool

只有当你为这个定理写一个证明时，编译器才会高兴……你可能猜到上面的算法就是证明。

一个有趣的观察是，算法几乎是由数据类型的形状决定的。假设您想对一棵树中的所有值求和:

sum(t) = { x                   if t = Leaf x
         , x + sum(l) + sum(r) if t = Node l x r
         }

每次你想在二叉树上写一个算法，你都会写上面这样的东西。这是相当机械和重复的。如果以后你扩展你的程序来处理玫瑰树呢？尝试？你不想写同样的算法，冒着犯错误的风险。人们会尝试想出一个沿着树向下走并组合其值的函数（从现在开始使用Haskell符号）：

walk :: (Int -> b) -> (b -> b -> b) -> Tree -> b
walk f g (Leaf x) = f x
walk f g (Node l x r) =
  let a = walk f g l
      b = walk f g r
  in g (g (f x) a) b

仅使用此函数，就可以在树上编写所有方式的遍历：

sum t      = walk id (+) t
search x t = walk (== x) (||) t

wal是这样一种循环模式，它已经被抽象化了。所有公开相同递归模式的数据结构都被称为可折叠的，并且实现通常如此明显，以至于您可以要求编译器为您编写它，如下所示：

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving (Foldable)

任何可折叠的数据结构都有一个求和的定义。

Answer 2

二进制搜索可以编写如下。类型可以更通用，因为我们只需要项目可以排序以在二进制树中存储/搜索。

我们访问每个节点，或者返回true，或者在1个子节点中搜索。

示例节点

   5
 /   \
3     7

让我们搜索 7.

我们首先访问根。自5！=7，我们测试一个子节点。自7日起

如果我们到达一片叶子，我们只需检查它是否包含搜索词。

search :: Ord a => a -> BinaryTree a -> Bool
search a (Leaf b) = compare a b == EQ
search a (Node left b right) 
  case compare a b of 
    EQ -> True
    LT -> search a left
    GT -> search a right