编辑#2:这整个问题和探索都是基于我错过了拉链的基本概念;从特定节点的角度来看,它们代表了数据结构中的透视图。因此,拉链始终是一对当前节点以及从该节点的角度来看树的其余部分的样子。我最初试图从拉链中生成一个全新的结构,而拉链本身就是我所需要的,一直以来。我将把这一切留给后代,希望其他人得到它的帮助(或者它可以作为对任何继任者的警告!)。
原始问题:
我正在尝试使用拉链来操纵树木。具体问题是我需要在运行时在任意树中匹配任意标准的两个节点之间生成路由。
我想我可以使用该函数通过调用当前位置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 函数只能将您带到树中的父位置,而忽略您与实际位置之间的任何兄弟姐妹。
我错过了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 的聊天深受影响,谢谢!