-3

考虑以下玫瑰树的定义： 树可以包含唯一的节点。

data NTree a = Nil | Node { root :: a, subtree :: [NTree a]} deriving Show
-- or just data NTree a = Nil | Node a [NTree a]

t1 :: NTree Int
t1 = Node 1 [Node 2 [ Node 5 [Nil], Node 6 [Nil], Node 7 [Nil]], Node 3 [Node 8 [Nil], Node 9 [Nil]], Node 4 [Nil]]
{-
t1:        1
        /  |  \
       /   |   \
     2     3     4
   / | \   | \
  5  6  7  8  9
-}

如何找到玫瑰树的给定节点的邻居数？示例我的意思：

--Function that finds the number of the neighbours of a given node
neighboursOf :: (Eq a) => NTree a -> a -> Int
--Examples:
print (neighboursOf t1 3) -- -> 3 (The neighbours are 1,8 and 9)
print (neighboursOf t1 1) -- -> 3 (The neighbours are 2,3 and 4)
print (neighboursOf t1 8) -- -> 1 (The neighbour is 3)
print (neighboursOf t1 10) -- -> error "Not existing node"

我不知道如何实现该功能

neighboursOf :: (Eq a) => NTree a -> a -> Int

你能帮我实现这个功能吗？

编辑： 我想出了这个解决方案：

data NTree a = Nil | Node {root :: a, subtree :: [NTree a] } deriving (Show , Eq)

neighborsOf :: (Eq a) => NTree a -> a -> Int
neighborsOf Nil _ = error "Empty tree"
neighborsOf tree element
    | helper tree element True == 0 = error "No such element"
    | otherwise = helper tree element True

helper ::(Eq a) => NTree a -> a -> Bool -> Int
helper Nil _ _ = 0
helper tree el isSuperior
    | root tree == el && isSuperior && subtree tree == [Nil] = 0
    | root tree == el && isSuperior = length $ subtree tree
    | root tree == el && subtree tree == [Nil] = 1
    | root tree == el = length (subtree tree) + 1
    | otherwise = helper' (subtree tree) el
        where 
            helper' :: (Eq a) => [NTree a] -> a -> Int
            helper' [] _ = 0
            helper' (tree:subtrees) el = helper tree el False  + helper' subtrees el

而且我认为这是一个非常糟糕的解决方案。你能给我一些改进的建议吗？

4

1 回答 1

1

好的，现在我们可以开始考虑了。所以你的邻居要么是节点的子节点，要么是节点的父节点。

您可以编写两个单独的函数，一个是childrenOf :: Node -> [Node]，另一个是parentOf :: Node -> [Node]，然后使用这两个函数的结果并将它们组合成您需要的函数。简单的。:)

树中的节点只能有一个父节点，那么为什么我指定列表[Node], 作为 的结果parentOf？总是只有一个父母吗？

于 2021-05-19T09:43:21.620 回答