6

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

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

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

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

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

我有两个问题：

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

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

4

2 回答 2

3

您不需要拉链来进行简单的树遍历。

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为并行版本），如果您尝试通过顺序化来节省工作，这将丢失。在顺序情况下，使用拉链肯定会更有效。

于 2013-10-10T00:42:12.513 回答
2

以下是如何在不假设任何有关树的布局的情况下实施第 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))

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

于 2013-10-10T19:28:09.263 回答