search - 二分木で要素を見つける

Question

私が二分木を持っていると仮定します：

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

値を検索してその子の数を返す関数を作成する必要があります。この値のノードがない場合は、-1を返します。BFSとDFSの両方を書き込もうとしていましたが、両方で失敗しました。

Answer 1

パターンマッチングはあなたの友達です。あなたはまたはのBstいずれかである可能性がEmptyあるNodeため、トップレベルでは、search関数は次のようになります。

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

Emptyツリーにターゲット値を含めることはできますか？ターゲット値があるNode場合は、ノード値（x上記）、leftサブツリー、サブツリー、rightまたはこれらの組み合わせのいずれかになります。

Bst「子の数を返す」とは、その値がターゲットであるルートの子孫の総数を意味すると思いますNode。これは、問題の興味深い組み合わせです。上記のように定義がパターンマッチングを使用する別の関数、たとえば、が必要になります。numChildren考慮事項：

1. Empty木には何人の子孫がいますか？
2. このNode場合、子孫xが必要なのでカウントされません。とサブツリーの子の数をカウントする関数があれば…leftright

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