使用Data.Tree.Zipper遍历玫瑰树

Question

我有一个玫瑰树结构,我用Data.Tree表示.树中的每个节点都标有(x,y)坐标.我需要实现一种方法,在树中找到最接近给定查询坐标的节点,并将子节点添加到该节点.

我设想将其分为两个操作:

1. 遍历树以查找最接近给定查询坐标的节点

2. 获取在先前遍历中找到的节点,并向其添加标有上述查询坐标的子节点

我能想到的唯一方法是使用Data.Tree.Zipper在步骤1中遍历树,然后在步骤2中使用该拉链在特定位置插入节点.

我有两个问题:

• 这是解决问题的有效方法吗？

• 如果是这样,我如何使用Data.Tree.Zipper中的函数来实现上面的步骤1？我发现树遍历很难实现,因为它需要两个维度的递归:深度和广度.

Answer 1

以下是如何在不假设树布局的情况下实现步骤 1 的方法。为了简单起见，我将挑选最小节点，而不是最小化某些功能的节点，但修改这个想法并不难。由于某种原因，rosezipper没有提供获取拉链的所有子项的操作，因此我们必须首先实现它。完成此操作后，想法就非常简单：对子级进行递归，然后选择当前位置或递归结果中的最小值。

import Data.List
import Data.Ord
import Data.Tree
import Data.Tree.Zipper

childrenAsList :: TreePos Full a -> [TreePos Full a]
childrenAsList = go . children where
    go z = case nextTree z of
        Nothing -> []
        Just z  -> z : go (nextSpace z)

minZipper :: Ord a => Tree a -> TreePos Full a
minZipper = go . fromTree where
    go z = minimumBy (comparing (rootLabel . tree))
                     (z:map go (childrenAsList z))

您当然不需要使用拉链来完成一些高效的事情，但这无疑是解决该问题的一种合理且好的方法。与两次遍历方法相比，这种方法的一个优点是它应该具有最大共享。