1

我正在尝试创建一个从表单的邻接列表构建树的函数{node [children]}。

(def adjacency
  {nil [:a]
   :a [:b :c]
   :b [:d :e]
   :c [:f]})

这应该导致

{nil {:a {:b {:d nil
              :e nil}
          :c {:f nil}}}}

但是我试过了，我无法让它工作。递归是我的一个弱点，我发现的大多数递归示例只处理列表上的递归，而不是树。

已编辑：由于在发布时没有编辑器和原始来源，原始数据集和结果无意中嵌套得太深。对于那个很抱歉。

4

2 回答 2

2

中的每个子图中只有一个条目adjacency。这是必要的吗？结果也出现了同样的问题tree。

我希望它会更清楚：

(def adjacency {:a [:b :c]
                :b [:d :e]
                :c [:f]})

所以解决方案是：

(defn tree [m root]
  (letfn [(tree* [l]
            (if (contains? m l)
              {l (into {} (map tree* (m l)))}
              [l nil]))]
    (tree* root)))

测试：

(tree adjacency :a)
=> {:a {:b {:d nil
            :e nil}
        :c {:f nil}}}

更新。如果您不需要将结果树作为嵌套映射

(defn tree [m root]
  (letfn [(tree* [l]
            (if (contains? m l)
              (list l (map tree* (m l)))
              (list l nil)))]
    (tree* root)))

(tree adjacency :a)
=> (:a ((:b ((:d nil)
             (:e nil)))
        (:c ((:f nil)))))
于 2013-01-20T07:15:24.333 回答
2

我通常更喜欢clojure.walk在处理树木时使用。我假设根节点在adjacency向量中是第一个。

(use 'clojure.walk)

(def adjacency
  [{nil [:a]}
   {:a [:b :c]}
   {:b [:d :e]}
   {:c [:f]}])

(prewalk
 (fn [x]
   (if (vector? x)
     (let [[k v] x lookup (into {} adjacency)]
       [k (into {} (map (fn [kk] [kk (lookup kk)]) v))])
     x))
 (first adjacency))

结果：{nil {:a {:b {:d {}, :e {}}, :c {:f {}}}}}

注意：空子元素表示为{}而不是nil，子元素也是地图而不是矢量，因为地图可以轻松导航此树。

于 2013-01-20T09:57:45.100 回答