2

我必须创建一个二叉搜索树，一个名为 Person 的数据类型，并且基本上将每个人插入到树中。问题是插入方法有一个优先类型，它在下面的代码中定义：

class Priorities a where  

     priority :: a -> Int  


instance Priorities a where  

     priority :: a -> Int

树的每个节点都是一个列表，并且插入是根据 Priorities 类中的优先级编号完成的，每个人都被赋予（在我的代码中，这个函数称为 insertTree）。

这是我到目前为止所做的事情：

data Tree => Tree a = EmptyTree  
            | Node a (Tree [a]) (Tree [a]) deriving (Show, Read, Eq)  

data Person = Person { name :: a
                 , age :: a
                 , handicapped :: a
                 } deriving (Eq)

这是我需要帮助的地方，因为我不知道如何进行此插入。我的意思是，我开始没问题，但是当我到达需要使用优先级值的部分时，我会感到困惑，以便知道我将在哪个节点（这是一个列表）中插入数据。

insertTree :: (Ord a) => Priorities priority -> Tree a -> a -> Tree a  
insertTree x EmptyTree x = Node x EmptyTree EmptyTree  
insertTree x (Node a left right) y  
            |x ==  = Node y left right  
            |x

我想问你的另一件事是，我怎样才能使数据类型 People 成为 Priorities 类的实例。

4

2 回答 2

1

如果我正确理解了您的问题，您的树类型应该是这样的：

data Tree a = EmptyTree
            | Node {
                nodePriority:: Int,
                nodeValues :: [a],
                leftChild :: Tree a,
                rightChild :: Tree a
              } deriving (Show, Read, Eq)

然后 insertTree 就像：

...
insertTree value (Node p values left right) =
  | priority value == p = "insert value in values"
  | priority value < p = "recurse into left branch"
  | otherwise = "recurse into right branch"

这个想法是左分支中的节点的优先级总是低于它的父节点，而右分支的节点总是比它的父节点具有相同或更高的优先级。例如，如果我按以下顺序插入优先级为 4 2 5 1 3 的对象，则会产生以下树：

    4
   / \
  2   5
 / \
1   3

最后，要使 Person 成为 Priorities 的实例，您可以执行以下操作：

instance Priorities Person where  
     priority p = age p -- I'm using age as an example, but you can put whatever function you want
于 2013-11-13T23:14:00.397 回答
0

所以基本上我的 insertTree 函数会是这样的：

insertTree value (Node p left values right)  
   | priority value == p = Node p left value right  
   | priority value < p = Node p left value (insertTree right value)  
   | otherwise = Node p (insertTree left value) value right
于 2013-11-13T23:50:05.677 回答