编辑 #2: 我错过了zipper的基本概念,即它们代表数据结构中从特定节点视角的一种透视图。因此,一个zipper始终是当前节点和从该节点视角看到的树的其余部分的一对。我最初尝试从zipper生成一个全新的结构,而实际上我所需要的只是zipper本身。希望这篇文章能够帮助其他人(或者成为任何接替者的警告!),我将其保留下来。
原始问题:
我正在尝试使用zippers操作树。具体问题是,我需要在运行时生成两个节点之间匹配任意条件的路由,这些节点位于任意树中。
我认为我可以使用path
函数通过在当前位置调用path
来获取到达该位置的路径。但是返回的路径似乎省略了到达该位置所需的最后一步(步骤)。
例如:
(def test-zip (vector-zip [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]]))
(-> test-zip
down right right down
right down right right
node)
该代码返回5
,但是
(-> test-zip
down right right down
right down right right
path)
提供
[[0 [1] [2 [3 [4] 5 [6 [7] [8]]]]] [2 [3 [4] 5 [6 [7] [8]]]] [3 [4] 5 [6 [7] [8]]]]
这并不是同一个位置(它缺少最后三个步骤的效果,down right right
)。
看起来路径函数只能让你到达树中父级位置,忽略了在你和实际位置之间的任何兄弟节点。
我是否误解了 path
函数的含义?我本以为,给定一棵树和一条路径,将该路径应用于树将使您到达路径的原始位置,而不是部分到达。
更新:我已使用以下函数定义将节点的路径从起始位置编译为结束位置:
(defn lca-path [start-loc end-loc]
(let [sczip (z/root start-loc)
start-path (z/path start-loc)
start-node (z/node start-loc)
end-path (z/path end-loc)
end-node (z/node end-loc)
lca-path (filter (set start-path) end-path)
lca-node [(last lca-path)]
lca-to-start (conj (vec (drop (count lca-path) start-path)) start-node)
lca-to-end (conj (vec (drop (count lca-path) end-path)) end-node)
]
(concat (reverse lca-to-start) lca-node lca-to-end))
)
在与@Mark Fisher的聊天中,我受到了很大的启发,谢谢!
3
、[4]
、5
和[6 [7] [8]]
,在这种情况下搜索范围不会太宽。但是,四个位置返回相同的路径是否不奇怪?我是否错过了在拉链中捕获位置路线的其他惯用方法? - Oliver Mooneypath
函数的功能吗?一旦您找到起始位置和结束位置,并在这两个位置上调用路径,您可以执行(filter (set start-path) end-path)
来获取两点的最低公共祖先。我还做了lca-to-start-parent (drop (count lca-loc) start-path)
以获取从最低公共祖先到起点的路径,以及(drop (count lca-loc) end-path)
另一条腿到终点。我喜欢您的自包含实现方式,以及如何使用identical?
导航到父位置... - Oliver Mooney