search - 在二叉树中查找元素

Question

假设我有一个二叉树：

data Bst a = Empty | Node (Bst a) a (Bst a)

我必须编写一个函数来搜索一个值并返回其子项的数量。如果没有具有此值的节点，则返回 -1。我试图同时编写 BFS 和 DFS，但我都失败了。

Answer 1

模式匹配是你的朋友。您Bst可以是Empty或 a Node，因此在顶层，您的search功能将是

search Empty = ...
search (Node left x right) = ...

一Empty棵树可能包含目标值吗？Node目标值（如果存在）将是节点值（上x图）、left子树中、right子树中——或者可能是这些的某种组合。

Bst通过“返回 [ing] 其子项的数量”，我假设您是指以 a 为目标的子节点的总数Node，这是一个有趣的问题组合。您将需要另一个函数，例如numChildren，其定义使用上述模式匹配。注意事项：

1. Empty一棵树有几个后代？
2. 在这种Node情况下，x不算数，因为您想要后代。如果你有一个函数来计算子树left和right子树中的孩子的数量……

Answer 2

这是一种方法。呼吸优先搜索实际上可能有点难以实现，而且这个解决方案 (findBFS) 非常复杂（附加到列表是 O(n)），但你会明白要点的。

首先，我决定拆分查找函数以返回节点元素匹配的树。这简化了拆分计数功能。此外，返回元素的数量比返回后代的数量更容易，如果找不到则返回 -1，因此numDesc函数依赖于 numElements 函数。

data Tree a = Empty
            | Node a (Tree a) (Tree a)

numElements :: Tree a -> Int
numElements Empty        = 0
numElements (Node _ l r) = 1 + numElements l + numElements r

findDFS :: Eq a => a -> Tree a -> Tree a
findDFS _ Empty                         = Empty
findDFS x node@(Node y l r) | x == y    = node
                            | otherwise = case findDFS x l of 
                                            node'@(Node _ _ _) -> node'
                                            Empty              -> findDFS x r

findBFS :: Eq a => a -> [Tree a] -> Tree a                                                                
findBFS x []                              = Empty
findBFS x ((Empty):ts)                    = findBFS x ts
findBFS x (node@(Node y _ _):ts) | x == y = node
findBFS x ((Node _ l r):ts)               = findBFS x (ts ++ [l,r])

numDescDFS :: Eq a => a -> Tree a -> Int
numDescDFS x t = numElements (findDFS x t) - 1

numDescBFS :: Eq a => a -> Tree a -> Int
numDescBFS x t = numElements (findBFS x [t]) - 1