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

如果两者相等，则第一棵树是第二棵树的子树，或者它是左子树或右子树的子树。

Haskell 仅在叶子中有值的二叉树

Haskell binary tree with values only in leaves

binary-tree

haskell