Бинарное дерево Haskell со значениями только в листьях

Question

Я хотел бы создать тип данных, который представляет собой двоичное дерево, которое имеет значения, хранящиеся только в листьях, а затем функцию sub, чтобы проверить, является ли дерево поддеревом другого дерева. Вот мой код, но я понятия не имел, как реализовать функцию sub.

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

makeBinTree :: [a] -> BinaryTree a 
makeBinTree lst = head $ mrg leaves 
where 
    leaves = map (\x -> Leaf x) lst 
    mrg [] = [] 
    mrg [x] = [x] 
    mrg (x:y:xs) = mrg ((Node x y) : mrg xs) 

sub :: Eq a => BinaryTree a -> BinaryTree a -> Bool 

Answer 1

Во-первых, вам нужна функция, чтобы увидеть, равны ли два дерева. Вы можете получить Eq или реализовать что-то рекурсивно как этот

eq :: Eq a => BinaryTree a -> BinaryTree a -> Bool 
eq (Leaf x) (Leaf y) = x == y 
eq (Node l1 r1) (Node l2 r2) = (l1 `eq` l2) && (r1 `eq` r2) 
eq _ _ = False 

С, что вы можете сделать

sub :: Eq a => BinaryTree a -> BinaryTree a -> Bool 
sub s (Leaf y) = s `eq` Leaf y 
sub s t@(Node l r) = s `eq` t || sub s l || sub s r 

Первое дерево является суб-дерево из второго, если оба равны или является суб- дерево левого или правого поддерева.