2 
data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Eq, Show)

unfoldTree:: (b -> Maybe (b, a, b)) -> b -> Tree a
unfoldTree f b =
    case f b of
      Nothing -> Leaf
      Just (lt, x, rt) -> Node (unfoldTree f lt) x (unfoldTree f rt)

鉴于以上两条信息，我被要求实现一个树构建功能。

我的尝试是

treeBuild :: Integer -> Tree Integer
treeBuild 0 = Leaf
treeBuild n = treeUnfold (\b -> if b < 2^n-1 
                then Just(2*b, b + 1, 2*b + 1) 
                else Nothing) 
                0

基本情况适用于 n = 0 工作正常但我知道该功能完全错误的情况。有人可以向我重新解释一下如何3-tuple Just工作吗？在正常展开中，a 中的第一个元素Just将是我想要的元素，第二个元素将用于继续展开，但这在 3 元组 Just 中如何工作？

作为示例输出： treeBuild 2 ----> Node (Node Leaf 0 Leaf) 1 (Node Leaf 2 Leaf)

编辑：我不完全确定 Just 在这里是如何工作的，对于Just(2*b, b + 1, 2*b + 1)b 从 0 开始的情况，它会变成Just(0, 1, 0)吗？我如何实际增加b？

4

1 回答 1

5

我认为您在粘贴 的定义时省略了一个空格unfoldTree。应该是这个吗？

展开树 fb =
    案例fb ...

本质上没有什么意义Maybe (b, a, b)，但在这种特殊情况下，您可以看到unfoldTree将元组中的项目绑定到lt、x和rt。中间值x用于创建节点，并lt用于rt为对 的递归调用播种unfoldTree。

为了解释您的示例输出，请注意n始终绑定到2. 的初始0参数treeUnfold意味着(\b -> ...)函数首先检查0 < 2^n-1，然后产生Just (2*0, 0+1, 2*0+1)。

中间值0+1是树中根节点的值。左子树的构建方式类似，除了bis now 2*0，右子树使用bas构建2*0+1。

你提到这是家庭作业，应该用2^n - 1节点构建一棵树。我猜这些Leaf值不算数，并且您想按广度优先顺序对这些节点进行编号，希望这个示例能让您熟悉。以下是如何做到这一点：

treeBuild :: Int -> Tree Int
treeBuild n = treeUnfold (\b -> 如果 b < 2^n - 1
                                   然后就是 (2*b+1, b, 2*b+2)
                                   其他没有）0

我得出的方法是绘制一棵深度为 3 的二叉树。我将从根开始的节点编号为0，左节点为1，右节点为2。底部节点从左到右编号，从 开始到4结束7。

现在模式是可见的：如果当前节点被编号b，他的左右节点分别被编号2*b+1和2*b+2。因为2^n - 1是 depth 树中的节点总数n，并且我按广度优先顺序对节点进行编号，返回Nothingwhenb >= 2^n-1确保我在将树填充到 depth 后停止n。

于 2013-03-21T02:56:45.950 回答