3

编辑#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 的聊天深受影响,谢谢!

4

1 回答 1

4

我认为你是对的,它是它路径的父级,这在查看这个站点时得到证实,path返回“从树根到当前位置上方的所有子树”。

对于您的结构,树是:

   A
 / | \
0  o  B
   | / \
   1 2  C __
       /|\  \
      3 o 5  o
        |   /|\
        4  6 o o
             | |
             7 8

所以标记为A,B,C的3个节点是导致5个父节点的父节点,它们是:

A: [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]]
B: [2 [3 [4] 5 [6 [7] [8]]]]
C: [3 [4] 5 [6 [7] [8]]]

这就是你得到的结果。

编辑:我创建了这个函数来搜索向量中的两个值并返回path它们之间的值。这有帮助吗?我不是拉链专家,所以这对我来说也是学习的。

(defn between [v s e]
  (let [zv (zip/vector-zip v)
        find-loc (fn [zv l]
                   (loop [loc zv]
                     (if (= l (zip/node loc))
                       loc 
                       (if (zip/end? loc)
                           nil
                           (recur (zip/next loc))))))
        sv (zip/vector-zip (-> (find-loc zv s) zip/up zip/node))
        e-in-sv (find-loc sv e)
        path-s-e (when (some? e-in-sv)
                   (zip/path e-in-sv))]
    path-s-e))

它找到起始值的父级和结束值的父级之间的路径,您可以像这样使用它:

(def sov [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]])
(between sov 2 6)
=> [[2 [3 [4] 5 [6 [7] [8]]]] [3 [4] 5 [6 [7] [8]]] [6 [7] [8]]]

我正在遍历树以找到起始值的父级,然后从其父级创建一个新拉链,以便从起点开始限制路径。辅助函数“find-loc”为您要查找的条目返回一个拉链,例如向量中的“5”。sv然后是包含起始值的父向量。

如果没有路径,则返回 nil,例如在 1 到 4 之间,您必须向上遍历 2 个元素。

5这是对您必须在最终节点(例如in )中找到值的评论的回应[3 [4] 5 [6 [7] [8]]],我认为您不需要这样做,但是如果没有您正在做的真实示例,很难评论。

顺便说一句,在向量中遍历/查找值的方法可能比自定义函数好得多,但正如我所说,拉链对我来说也很新。

于 2015-05-08T13:22:47.030 回答