用Data.Tree.Zipper遍歷玫瑰樹

我有一個玫瑰樹結構，我用Data.Tree表示。樹中的每個節點都標有（x，y）座標。我需要實現一種方法來查找樹中最接近給定查詢座標的節點，並向該節點添加一個子節點。用Data.Tree.Zipper遍歷玫瑰樹

我設想將這種成兩個操作：

遍歷樹找到最接近給定查詢座標
採取事先遍歷找到的節點，並添加到節點它是一個孩子與上述查詢座標

我能想到這樣做的唯一方法是在第1步中使用Data.Tree遍歷樹.Zipper，然後在步驟2中使用該拉鍊將節點插入特定位置。

我有兩個問題：

這是解決這個問題的有效途徑？
如果是這樣，我該如何使用Data.Tree.Zipper中的函數來實現上面的第1步？我發現樹遍歷很難實現，因爲它需要在兩個維度上進行遞歸：深度和廣度。

來源

2013-10-09 giogadi

告訴我們關於第1步的更多信息。樹是否以任何方式組織？ –

就此問題而言，沒有任何兒童或父母與子女之間的相關關係。我對執行完整的樹遍歷來搜索最近的節點感到滿意。 – giogadi

下面介紹如何在不假設任何關於樹的佈局的情況下實現步驟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-10 19:28:09

你不需要拉鍊來做簡單的樹遍歷。

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-10 00:42:12 Fixnum

這太棒了！這絕對有效，但是你知道在一次樹遍歷中是否有辦法做到這一點？在這種情況下，需要進行一次遍歷才能找到最近的節點，然後再次進行遍歷以「重新找到」最近的節點。我可能最終會實現你的解決方案，但我很好奇，如果在一次遍歷中有一種慣用的方法來實現，即使它很複雜。 – giogadi

我確定某些基於拉鍊或基於延續的解決方案會起作用。 – Fixnum

我對這個建議感到非常困惑。是什麼讓這比使用拉鍊更好？看起來它會有比較糟糕的表現。 –

用Data.Tree.Zipper遍歷玫瑰樹

回答

相關問題