如果在 Haskell 中可用，则将节点插入到最高级别的节点

Question

我创建了一棵树，它的数据类型是：

data Tree = Empty | Node Int Int Tree Tree Tree

我的第一个

Int

是实际数据。第二个

Int

是孩子的数量，意思是这个节点可以存储多少个孩子。即使是三叉树，如果孩子的数量是两个，那么它应该存储两个孩子。

我的问题是，在我创建了一个函数

inserter tree node

之后，它将从列表中获取节点，并将插入到可用的最高级别节点（这意味着如果孩子的数量还没有满）。这是一个例子：

                              a
                             / \
                            b   c
                           / 
                          d
                         /
                        e

例如，'d'只能存储两个孩子（它的第二个

Int

值是二），但它有一个孩子。此外，'b' 只能存储两个孩子，但它有一个孩子。现在，我的列表有两个节点，我将插入这些节点。首先，我需要填写'd'，然后我将填写'b'节点，这样他们就会达到他们的孩子数量。 （比方说我的名单

[k,l]

）。我的过程的结束将是：

                              a
                             / \
                            b   c
                           / \
                          d   l
                         / \
                        e   k

我想实现经典的递归方法：

inserter (Node _ num first second third) node
 | num/=0     = Node _ num (inserter first node) (inserter second node) (inserter third node)
 | otherwise  = insert (Node _ num first second third) node

（

insert

是我写的另一个函数，我确实从列表部分拿来使用这个函数）

当我这样做时，它将插入第一个可用节点，我需要通过直到找到可用的最高级别节点。你能给我一个想法，或者我可以遵循的方式吗？

Answer 1

将问题分解成更小的部分。如果

inserter

正在插入节点列表，首先尝试编写一个函数（我们称之为

inserter1

），它仅在最高可用级别插入 1 个节点。然后你可以根据那个函数写

inserter

。

从类型签名开始。我在这里假设当你说“插入一个节点”时，你的意思是“插入一棵树”。然后

inserter1

有类型

Tree -> Tree -> Tree

.

要定义

inserter1

，首先考虑最简单的基本案例并从那里开始工作。最简单的情况是插入一棵空树：

inserter1 :: Tree -> Tree -> Tree
inserter1 Empty node = node

下一个最简单的情况是插入到具有一层的树中：

inserter1 (Node i n Empty Empty Empty) node
  | n > 0     = Node i n node Empty Empty -- There is room
  | otherwise = _ -- What to do when there is no room? 

这里我们遇到了一个问题，如果没有空间可以插入东西，返回什么。如果

n

是

0

，我们就不能成功插入

node

！这表明我们应该在返回类型中有一个“插入失败”的概念。一个常见的模式是使用

Maybe

，这意味着将

inserter1

的类型更改为

Tree -> Tree -> Maybe Tree

。现在我们可以在第二种情况下返回

Nothing

：

inserter1 :: Tree -> Tree -> Maybe Tree
inserter1 Empty node = Just node
inserter1 (Node i n Empty Empty Empty) node
  | n > 0     = Just (Node i n node Empty Empty)
  | otherwise = Nothing

递归情况是当您在当前级别的插入位置有多个选择时，即在此级别上有可用的

Empty

s 和可能更可取的子节点。在这种情况下，我们想先尝试插入到子节点中，只有在插入到子节点失败（因为它们已满）时才求助于此级别的插入。这是一个子节点的样子：

inserter1 (Node i n t1 Empty Empty) node =
  -- Should we insert into child `t1` or replace an `Empty` on this level? Inserting into child nodes is preferable, so try it first.
  case inserter1 t1 node of
    -- The insertion to `t1` worked and became `t1'`, so replace it and we're done!
    Just t1' -> Just (Node i n t1' Empty Empty)
    -- `t1` must have been full, so see if there is room to insert on this level
    Nothing
      -- There is room
      | n > 1 -> Just (Node i n t1 node Empty)
      | otherwise -> Nothing

希望这能给你一些指导，帮助你完成定义。我建议为两个非空孩子添加一个案例，然后为三个非空孩子添加一个案例。试着先让它工作，即使感觉你写了太多的案例。一旦你有了一些工作，通常更容易看到如何简化它。