用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))

你当然不需要用拉链来做一些有效率的事情，但这肯定是一个合理和好的方法来解决这个问题。与两次遍历方法相比，这种方法的一个优点是它应该具有最大的共享。

Answer 2

你不需要拉链来做简单的树遍历。

import Data.Foldable (minimumBy)
import Data.Function (on)
import Data.Tree

addPt :: (Eq a, Ord b) => (a -> a -> b) -> a -> Tree a -> Tree a
addPt dist p t = down t
  where
    down (Node a xs)
      | a == closest = Node a (Node p []:xs)
      | otherwise    = Node a (map down xs)
    closest = minimumBy (compare `on` dist p) t

如果重复minimumBy返回的最接近的点，这将多次添加这个点，并且可能会稍微提高一些效率，因为down总是完全遍历树，即使它很早就找到了元素。为了解决这两个问题，您可以编写一个函数，依次考察每个分支，返回(可能是增广的)分支，再加上一个Bool，以指示是否添加了点。另一方面，addPt自然具有高度并行性(模块化使用Data.Tree中的链接列表，并将minimumBy替换为并行版本)，如果您试图通过顺序化来节省工作，这将丢失。在顺序的情况下，使用拉链肯定会更有效。